快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

基本思想

快速排序的基本思想：挖坑填数+分治法。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

  1. 从数列中挑出一个元素，称为”基准”（pivot）。
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
Java快速排序 - 图1

代码实现

用伪代码描述如下：

  1. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
  2. j—，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
  3. i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

  4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中

    1. public static void sort(int[] a, int low, int high) {
    2.  //已经排完
    3.  if (low >= high) {
    4.      return;
    5.  }
    6.  int left = low;
    7.  int right = high;
    9.  //保存基准值
    10.  int pivot = a[left];
    11.  while (left < right) {
    12.      //从后向前找到比基准小的元素
    13.      while (left < right && a[right] >= pivot)
    14.          right--;
    15.      a[left] = a[right];
    16.      //从前往后找到比基准大的元素
    17.      while (left < right && a[left] <= pivot)
    18.          left++;
    19.      a[right] = a[left];
    20.  }
    21.  // 放置基准值，准备分治递归快排
    22.  a[left] = pivot;
    23.  sort(a, low, left - 1);
    24.  sort(a, left + 1, high);
    25. }

    总结

    快速排序是不稳定的排序。

  • 快速排序的时间复杂度为O(nlogn)。
  • 当n较大时使用快排比较好，当序列基本有序时用快排反而不好。