快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

起源

东尼·霍尔(C.R.A.Hoare)于1962年提出。

思想

分治法

时间复杂度

平摊O(N*logN)，最坏O(n²)

最坏情况何时发生？

数组已是排好序的（无论是正序，还是倒序，或者相等）。

步骤

• 先从数列中取出一个数作为基准数。
• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 再对左右区间重复第二步，直到各区间只有一个数。  

动图演示

代码实现

int Paritition(int num[], int l, int r) {
  int pivot = num[l];
  while (l < r) {
    while (l < r && num[r] >= pivot) {
      --r;
    }
    num[l] = num[r];
    while (l < r && num[l] <= pivot) {
      ++l;
    }
    num[r] = num[l];
  }
  num[l] = pivot;

  return l;
}

void QuikSort(int num[], int l, int r) {
  if (l < r) {
    int pivot = Paritition(num, l, r);
    QuikSort(num, l, pivot - 1);
    QuikSort(num, pivot + 1, r);
  }
}

void main(){
  int num[5] = {1,5,4,2,3};
  QuikSort(num,0,4);
}