快速排序的思想非常简单，在待排序的数组中，先找到一个数字作为基准数，为了方便，一般选择数组的第一项作为基准数。接下来需要把这个待排序的数组中小于基准数的元素移动到待排序的数组的左边，把大于基准数的元素移动到待排序数组的右边。这时，左右两个分区的元素就相对有序了，接着把两个分区的元素的分别按照上面两个步骤继续对两个分区找到基准数，然后移动，直到各分区只有一个数时为止。

代码实现


  1. public class QuickSort {
  3.     public static Integer[] sort(Integer[] array) {
  4.         sort(array, 0, array.length - 1);
  5.         return array;
  6.     }
  8.     /**
  9.      * @param a
  10.      * @param lo
  11.      * @param hi
  12.      */
  13.     private static void sort(Integer[] a, int lo, int hi) {
  14.         if (hi <= lo) return;
  15.         int j = partition(a, lo, hi);
  16.         sort(a, lo, j - 1);
  17.         sort(a, j + 1, hi);
  18.     }
  20.     /**
  21.      * 辅助函数：用于交换两个值
  22.      *
  23.      * @param array
  24.      * @param a
  25.      * @param b
  26.      */
  27.     public static void exchange(Integer[] array, int a, int b) {
  28.         int tmp = array[a];
  29.         array[a] = array[b];
  30.         array[b] = tmp;
  31.     }
  33.     /**
  34.      * 辅助函数：用于交换元素
  35.      *
  36.      * @param valueA
  37.      * @param valueB
  38.      * @return
  39.      */
  40.     public static Boolean less(Integer valueA, Integer valueB) {
  41.         return valueA < valueB;
  42.     }
  44.     /**
  45.      * 辅助函数：切分
  46.      *
  47.      * @param a
  48.      * @param lo
  49.      * @param hi
  50.      * @return
  51.      */
  52.     private static int partition(Integer[] a, int lo, int hi) {
  53.         int i = lo, j = hi + 1;
  54.         Integer v = a[lo]; // 比较元素
  55.         while (true) {
  56.             // 扫描左右，检查扫描是否结束并交换元素
  57.             while (less(a[++i], v)) if (i == hi) break;
  58.             while (less(v, a[--j])) if (j == lo) break;
  59.             if (i >= j) break; // 结束外层循环
  60.             exchange(a, i, j);
  61.         }
  62.         exchange(a, lo, j); // 将 v = a[j] 放到正确的位置
  63.         return j; // a[lo..j-1] <= a[j] <= a[j+1..hi]
  64.     }
  66.     public static void main(String[] args) {
  67.         Integer[] array = new Integer[10];
  68.         for (int i = 0; i < array.length; i++) {
  69.             array[i] = (int) Math.floor((Math.random() * 10) + 1);
  70.         }
  71.         System.out.println(Arrays.toString(array)); // [9, 3, 2, 2, 6, 2, 5, 9, 1, 2]
  72.         System.out.println(Arrays.toString(sort(array))); // [1, 2, 2, 2, 2, 3, 5, 6, 9, 9]
  73.     }
  74. }

改进快排的两个方法

切换到插入排序

对于小数组，快速排序比插入排序慢。这是因为递归，快速排序的 sort() 方法在小数组中也会调用自己。

将 sort() 方法中的 if(hi <= lo) return; 改成 if(hi <= lo + M) Insertion.sort(a, lo, hi); return; 其中 M 取值范围是 5 ~ 15 之间。

三取样切分

这个方法适用于包含大量重复元素的数组。

  1. public class Quick3way {
  3.     public static Comparable[] sort(Comparable[] array) {
  4.         sort(array, 0, array.length - 1);
  5.         return array;
  6.     }
  8.     /**
  9.      * 辅助函数：用于交换两个值
  10.      *
  11.      * @param array
  12.      * @param a
  13.      * @param b
  14.      */
  15.     public static void exchange(Comparable[] array, int a, int b) {
  16.         Comparable tmp = array[a];
  17.         array[a] = array[b];
  18.         array[b] = tmp;
  19.     }
  21.     private static void sort(Comparable[] a, int lo, int hi) {
  22.         if (hi <= lo) return;
  23.         int lt = lo, i = lo + 1, gt = hi;
  24.         Comparable v = a[lo]; // v 始终都是不变的
  25.         while (i <= gt) {
  26.             int cmp = a[i].compareTo(v);
  27.             if (cmp < 0) exchange(a, lt++, i++);
  28.             else if (cmp > 0) exchange(a, i, gt--);
  29.             else i++;
  30.         } // 现在 a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]成立
  32.         System.out.println("***************************");
  33.         System.out.println(Arrays.toString(a));
  34.         System.out.println("***************************");
  36.         sort(a, lo, lt - 1);
  37.         sort(a, gt + 1, hi);
  38.     }
  40.     public static void main(String[] args) {
  41.         Integer[] array = new Integer[10];
  42.         for(int i = 0; i < array.length; i++) {
  43.             Double v = Math.floor((Math.random() * 3) + 1);
  44.             array[i] = v.intValue();
  45.         }
  46.         System.out.println(Arrays.toString(array)); // [1, 1, 1, 3, 2, 3, 3, 3, 3, 1]
  47.         System.out.println(Arrays.toString(sort(array))); // [1, 1, 1, 1, 2, 3, 3, 3, 3, 3]
  49.     }
  50. }

参考：