快速排序

快速排序(Quicksort)，简称快排，是一种排序算法。在平均状况下，排序n个项目要O(n/logn)次比较。在最坏状况下则需要O(n^{2})次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

思想

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

  • 从数列中挑出一个元素，称为”基准”（pivot）。
  • 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  • 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
  • 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

递归实现

  • Java
    1. // 递归方式
    2.   private void qSort(int[] arr, int head, int tail) {
    3.       // 输入检查
    4.       if (arr == null || arr.length <= 1 || head >= tail) {
    5.           return;
    6.       }
    7.       int i = head, j = tail;
    8.       // 取中间数为基准数
    9.       int pivot = arr[(head + tail) / 2];
    10.       while (i < j) {
    11.           while (arr[i] < pivot) {
    12.               ++i;
    13.           }
    14.           // 这里如果加上等于符号，则会数组导致越界
    15.           while (arr[j] > pivot) {
    16.               --j;
    17.           }
    18.           if (i < j) {
    19.               int temp = arr[i];
    20.               arr[i] = arr[j];
    21.               arr[j] = temp;
    22.               ++i;
    23.               --j;
    24.           } else if (i == j) {
    25.               ++i;
    26.           }
    27.       }
    28.       qSort(arr, head, j);
    29.       qSort(arr, i, tail);
    30.   }

循环方式

  1. //循环方式：使用容器缓存后续需要排序的子数组索引。
  2.     private void qSort2(int[] arr) {
  3.         // 输入检查
  4.         if (arr == null || arr.length <= 1) {
  5.             return;
  6.         }
  7.         Stack<Integer> cache = new Stack<>();
  8.         pushArrIndex(cache, 0, arr.length - 1);
  9.         while (!cache.empty()) {
  10.             int tail = cache.pop();
  11.             int start = cache.pop();
  12.             int i = start, j = tail;
  13.             // 取中间数为基准数
  14.             int pivot = arr[(start + tail) / 2];
  15.             while (i < j) {
  16.                 while (arr[i] < pivot) {
  17.                     ++i;
  18.                 }
  19.                 while (arr[j] > pivot) {
  20.                     --j;
  21.                 }
  22.                 if (i < j) {
  23.                     int temp = arr[i];
  24.                     arr[i] = arr[j];
  25.                     arr[j] = temp;
  26.                     ++i;
  27.                     --j;
  28.                 } else if (i == j) {
  29.                     ++i;
  30.                 }
  31.             }
  32.             if (start < j) {
  33.                 pushArrIndex(cache, start, j);
  34.             }
  35.             if (i < tail) {
  36.                 pushArrIndex(cache, i, tail);
  37.             }
  38.         }
  39.     }
  41.     private void pushArrIndex(Stack<Integer> stack, int start, int tail) {
  42.         // 先pushstart，取出来时先取到的是end
  43.         stack.push(start);
  44.         stack.push(tail);

小结

快排主要思想就是分治法，常用递归解法，如果数据量大可考虑使用循环解法，避免方法栈溢出。