QuickSort（快速排序）原理及C++代码实现

快速排序可以说是最重要的排序，其中延伸的思想和技巧非常值得我们学习。

快速排序也使用了分治的思想，原理如下：

分解：数组A[p..r]被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中计算下标q也是划分过程的一部分。

解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。

合并：因为子数组都是原址排序的，所以不需要合并操作，数组A[p..r]已经有序。

只要划分不是极端的，那么快速排序的时间复杂度为O(nlgn)，否则时间复杂度为θ（n2）。

可以利用随机化思想（随机选择主元）来使快速排序的期望时间复杂度达到O(nlgn)。

快速排序不是稳定排序。

代码如下：（仅供参考）

 1 int Partition(int * const begin, int * const end) { //lomuto划分
 2     int i = -1;
 3     for (int j = 0; j < (end - begin); ++j) {
 4         if (*(begin + j) <= *(end - 1)) {       //以最后一个值为关键值划分
 5             ++i;
 6             swap(*(begin + i), *(begin + j));
 7         }
 8     }
 9     return i;
10 }
11 
12 void QuickSort(int * const begin, int * const end) {
13     if (begin >= end - 1)
14         return ;
15     int mid = Partition(begin, end);
16     QuickSort(begin, begin + mid);    //调用的是lomute划分，因为lomuto划分结束以后
17     QuickSort(begin + mid + 1, end);  //mid一定在它应该在的位置
18 }

1 void QuickSort(int * begin, int * const end) {  //尾递归
2     while (begin < end - 1) {
3         int mid = Partition(begin, end);
4         QuickSort(begin, begin + mid);    //调用的是lomute划分
5         begin = begin + mid + 1;
6     }
7 }

另外一种划分方法：

 1 int Partition(int * const begin, int * const end) { //hoare划分
 2     int key = *begin;         //以第一个值为关键值划分
 3     int i = -1, j = end - begin;  //i, j根本不会越界
 4     while (1) {
 5         for (++i; *(begin + i) < key; ++i); //可看做do{}while；
 6         for (--j; *(begin + j) > key; --j);
 7         if (i < j)
 8             swap(*(begin + i), *(begin + j));
 9         else
10             return j;
11     }
12 }
13 
14 void QuickSort(int * const begin, int * const end) {
15     if (begin >= end - 1)
16         return ;
17     int mid = Partition(begin, end);
18 
19     QuickSort(begin, begin + mid + 1);   //调用hoare划分，因为hoare划分只能保证
20     QuickSort(begin + mid + 1, end);     //mid(包括mid）以前的元素小于等于mid以后的元素
21 }