图解Java排序算法之快速排序的三数取中法

编辑: admin 分类: java 发布时间: 2021-11-15 来源:互联网
目录
  • 基本步骤
    • 三数取中
    • 根据枢纽值进行分割
  • 代码实现
    • 总结

      基本步骤

      三数取中

      在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。

      根据枢纽值进行分割

       

      代码实现

      package sortdemo;
      import java.util.Arrays;
      /**
       * Created by chengxiao on 2016/12/14.
       * 快速排序
       */
      public class QuickSort {
          public static void main(String[] args) {
              int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
              quickSort(arr, 0, arr.length - 1);
              System.out.println("排序结果:" + Arrays.toString(arr));
          }
          /**
           * @param arr
           * @param left  左指针
           * @param right 右指针
           */
          public static void quickSort(int[] arr, int left, int right) {
              if (left < right) {
                  //获取枢纽值,并将其放在当前待处理序列末尾
                  dealPivot(arr, left, right);
                  //枢纽值被放在序列末尾
                  int pivot = right - 1;
                  //左指针
                  int i = left;
                  //右指针
                  int j = right - 1;
                  while (true) {
                      while (arr[++i] < arr[pivot]) {
                      }
                      while (j > left && arr[--j] > arr[pivot]) {
                      }
                      if (i < j) {
                          swap(arr, i, j);
                      } else {
                          break;
                      }
                  }
                  if (i < right) {
                      swap(arr, i, right - 1);
                  }
                  quickSort(arr, left, i - 1);
                  quickSort(arr, i + 1, right);
              }
          }
          /**
           * 处理枢纽值
           *
           * @param arr
           * @param left
           * @param right
           */
          public static void dealPivot(int[] arr, int left, int right) {
              int mid = (left + right) / 2;
              if (arr[left] > arr[mid]) {
                  swap(arr, left, mid);
              }
              if (arr[left] > arr[right]) {
                  swap(arr, left, right);
              }
              if (arr[right] < arr[mid]) {
                  swap(arr, right, mid);
              }
              swap(arr, right - 1, mid);
          }
          /**
           * 交换元素通用处理
           *
           * @param arr
           * @param a
           * @param b
           */
          private static void swap(int[] arr, int a, int b) {
              int temp = arr[a];
              arr[a] = arr[b];
              arr[b] = temp;
          }
      }

      排序结果

      [1, 2, 3, 4, 5, 6, 7, 8]

      总结

      快速排序是一种交换类的排序,它同样是分治法的经典体现。在一趟排序中将待排序的序列分割成两组,其中一部分记录的关键字均小于另一部分。然后分别对这两组继续进行排序,以使整个序列有序。在分割的过程中,枢纽值的选择至关重要,本文采取了三位取中法,可以很大程度上避免分组"一边倒"的情况。快速排序平均时间复杂度也为O(nlogn)级。

      本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注自由互联的更多内容!