排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

这是典型的分治思想，即分治法。

快速排序由于排序效率在同为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);
}