5、前后指针版本
5.1 实现思路
我们规定排升序，排序数组名称为a，基准值 key。
1.选出一个key，key可以是需要排序的数组中任意一个元素，我们依然选key为a[left]；
2.定义一个prev指针，和一个cur指针，初始化 prev 指向数组首部位置，cur 指向 prev 的下一个位置。cur先走，cur 找小于 key 的元素，找到之后停下来，让 prev++，然后交换 (a[cur], a[prev])。交换完继续往后走，cur 找的值不小于 key，cur继续往后走，找到后让 prev++，交换 (a[cur], a[prev])，不断重复此步骤；
3.当cur走完整个数组的时候，交换(a[left], a[prev])，这时key的最终位置就确定下来了。key 将数组分为左右两个子区间，左子区间小于 key，右子区间大于 key；
4.左右子区间继续重复前 3 步骤，递归下去就实现了数组的排序。
5.2 思路图解
这里不断交换其实是将小于 key 的值一直在往前抛，把大于 key 的值往后抛，cur与prev 之间的值其实就是大于 key 的所有值，不断交换就实现了最终以 key 划分的左右区间，左区间小于 key，右区间大于 key。
5.3 前后指针法代码实现
// 快速排序前后指针法 int PartSort3(int* a, int left, int right) { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
5.4 前后指针法代码测试
// 快速排序前后指针法 int PartSort3(int* a, int left, int right) { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } void test() { int a[] = { 6,3,2,1,5,7,9 }; QuickSort(&a, 0, sizeof(a) / sizeof(int) - 1); Print(&a, sizeof(a) / sizeof(int)); } int main() { test(); return 0; }
6、时间复杂度分析
6.1 最好情况
上面的三种情况下，最好情况时间复杂度是O(N* logN)。
每次 key 被排到区间的中间位置，像二叉树一样要递归 logN 次，每一次的子区间排序的时间复杂度是O(N)，所以最好的情况就是O(N * logN)。
6.2 最坏情况
当数组有序的时候排序，无论 key 选最左边还是最右边，时间复杂度都是O(N^2)。
7、优化快速排序
快速排序的优化有两种思想：
1.我们对选key法可以进行优化；
2.递归到小的子区间，我们可以考虑使用插入排序，也称小区间优化。
7.1 选 key 优化
选 key 优化主要是针对数组有序，或者是接近有序。
对选 key 的优化我们有两种思路：
1.随机选 key；
2.三数取中选 key。（拿出left, mid, right，在下标为这三个位置的数中选出一个中间值作为 key）。
第一种思路是不可控的，所以第二种选 key 的思路才是最合适的。
下面是三数取中的优化代码：
int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] < a[right]) return right; else return left; } else //a[left] > a[mid] { if (a[mid] > a[right]) return mid; else if (a[left] > a[right]) return right; else return left; } } int PartSort3(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; }
我们取到中后，将该数字与 a[left]交换，依旧用之前的前后指针法的思路是没有问题的。霍尔版本与挖坑法是一样的优化方法。
如果我们不做三数取中的优化，当数组是有序或者接近有序的时候，时间复杂度会是最坏情况，O(N^2)。经过三数取中后，如果数组是有序的，时间复杂度仍是O(N * logN)。
7.2 小区间优化
在递归的时候，我们之前画的图中不难看到，在不断的划分的时候，到后面划分的越来越多了，当数据量特别大的时候，对栈的消耗会很大，会造成栈溢出的风险。因此，当划分到一定的程度，我们不再划分，直接选择插入排序。一般的情况下，当我们的子区间数据个数为10的时候，我们就不再递归了，直接就用插入排序。
实现代码：
// 插入排序 //时间复杂度（最坏）：O(N^2) -- 逆序 //时间复杂度（最好）：O(N) -- 顺序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[i + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } } int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] < a[right]) return right; else return left; } else //a[left] > a[mid] { if (a[mid] > a[right]) return mid; else if (a[left] > a[right]) return right; else return left; } } // 快速排序前后指针法 //[left, right] int PartSort3(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; } void QuickSort(int* a, int left, int right) { //子区间只有一个值，或者子区间不存在的时候递归结束 if (left >= right) return; //小区间优化 if (right - left + 1 < 10) { InsertSort(a + left, right - left + 1); } int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
这两种优化的方式在时间与空间两个方面都有一定程度的提升，但快速排序的本质没有改变，优化只是在原有的思想上锦上添花。
