“田家少闲月，五月人倍忙”
“夜来南风起，小麦覆陇黄”
猛戳订阅🍁🍁 👉 纯C详解数据结构专栏 👈 🍁🍁
这里是目录
快速排序
一、经典1962年Hoare法
1.单趟排序
2.递归左半区间和右半区间
3.代码实现
二、填坑法(了解)
1.单趟思路
2.代码实现
三、双指针法(最佳方法)
1.单趟排序
2.具体思路
3.代码递归图
4.代码实现
四、三数取中优化(最终方案)
1.三数取中
2.代码实现(最终代码)
五、时间复杂度(重点)
1.最好情况下
2.最坏情况下
3.空间复杂度
六、非递归写法
1.栈模拟递归快排
2.队列实现快排
浅浅总结下
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
所以快速排序有种方法是以他的名字命名的。
相比70年前的祖师爷级的 大佬 来说，今天我们学习快速排序的成本已经非常低了。今天的我们的是站在巨人的肩膀上学习快速排序。
快速排序有三种方法实现，我们 都 需要掌握。
一、经典1962年Hoare法
让我们来看看1962年祖师爷发明的快排吧。
什么是快速排序？给你以下代码，请你完善快速排序，你将怎么完善？
快速排序：顾名思义，它比较快，整体而言适合各种场景下的排序。缺陷相较于其他排序小。且大部分 程序语言 排序的库函数 的 源代码都是由快速排序实现的
void QuickSort(int* a, int left, int right) { //请你完善以下代码 } int main() { int arr[] = {6,1,2,7,9,3,4,5,10,8}; int sz = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, sz-1); return 0; }
具体实现：
Hoare法和二叉树的**前序遍历(根 左子树 右子树)**简直一模一样。
整体思路：
1.先进行一趟排序。
2.进行左半区间(左子树)递归。
3.进行右半区间(右子树)递归。
1.单趟排序
所有的排序的思想：就是先考虑单趟的排序，再合成n躺排序。这是毋庸置疑的，因为这样的思想很自然。
对于单趟排序，也有一个思路。可以说算是规定吧，这是祖师爷Hoare的规定。
为了好理解思路，以下思路是整体上的思路，写出来的程序还是有bug的。具体细节需要后期修改。
一定要按照规定走哦，不要问那么多为什么。按照规定走你就知道为什么要这么做了。
总体思路规定：
1.设置一个基准值key，key一般为左边第一个数的下标。定义左指针left和有指针right分别指向第一个和最后一个。
2.先让右边的right指针往左走，一直找比key所指向小的数，找到后就停下。
3.紧接着让left指针往右走，一直找比key所指向大的数，找到后就停下。
4.如果第2步的right和第3步left都找到了，则交换swap两者的值。然后继续循环2和3步，直到left >= right为止。
5.此时left = right, 交换left和right相遇的位置的值 与 key位置上的值。
此时，Hoare 的单趟排序完成。产生的效果是key作为分割线，把大小分割开了，比key所指向值小的在key左边，比key所指向值大的在key右边。
2.递归左半区间和右半区间
对于单趟来说。
单趟排完之后，key已经放在正确的位置了。
如果左边有序，右边有序，那么我们整体就有序了。
那左边和右边如何有序呢？
解释：分治解决子问题。相当于二叉树。
一趟排序完成后，再对左半区间进行单趟排序，一直递归到什么时候结束呢？
解释：递归到左半区间只有一个值的时候，或者为空的时候递归结束。
这个过程适合用 画递归图 来查看。
由于数据是10个数，递归图庞大。所以此处省略。下面双指针法有具体递归图。
3.代码实现
具体代码实现和你想的总是那么不同。因为特殊情况确实是存在，且还是那么离谱。
我认为这个题难在了边界问题，边界问题要时刻注意！。
特殊情况1：当排以下数据时，我只是把6改了，这样会导致right和left直接不走了。
{6,1,2,7,9,3,4,5,10,6}
特殊情况2：当排以下数据时，会发生left找不到最大的值导致越界。
{5,4,3,2,1}
改动如下。
//快速排序Hoare int PartSort(int* a, int left,int right) { int key = left; while (left < right) { while (left < right && a[right] >= a[key]) { --right; } while (left < right && a[left] <= a[key]) { ++left; } swap(&a[left], &a[right]); } swap(&a[left], &a[key]); return left; } void QuickSort(int* a, int left, int right) { //当有个区间为空的时候right-left会小于0。 if (right <= left) return; int div = PartSort(a, left, right); QuickSort(a, left, div-1); QuickSort(a, div+1, right); } int main() { int arr[] = {6,1,2,7,9,3,4,5,10,8}; int sz = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, sz-1); return 0; }
二、填坑法(了解)
和Hoare法思想类似，大差不差，没什么区别。相比Hoare法较好理解。因为挖坑填坑思想很生动形象，所以较好理解。
1.单趟思路
单趟思路：
1.先保存key的值。让左边的key做坑(pit)，让右边找比key小的，然后填到坑中。
2.然后让那个小的做坑，再让左边找比key大的，找到后填到坑中。依次循环，直到right和left相遇。
3.相遇后，把key的值填到相遇的位置。
这时，单趟循环结束。
2.代码实现
和Hoare法相似，只是少了交换的步骤。
注意：要事先把key的值保存下来。
int PartSort(int* a, int left, int right) { int keyval = a[left]; int pit = left; while (left < right) { while (left < right && a[right] >= keyval) { right--; } a[pit] = a[right]; pit = right; while (left < right && a[left] <= keyval) { left++; } a[pit] = a[left]; pit = left; } a[pit] = keyval; return left; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int div = PartSort(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } int main() { int arr[] = { 6,1,2,7,9,3,4,5,10,8 }; int sz = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, sz-1); return 0; }
三、双指针法(最佳方法)
1.单趟排序
和以上两种方法的不同之处只有单趟排序，也就是PartSort函数的部分.
优点：有了双指针的优化，不需要考虑 边界问题！写代码不易出错。
代码好写，不好理解。代码极为简单，只需五行。
双指针法也称快慢指针法，两个指针一前一后
2.具体思路
对于排6,3,2,1,5,4的升序来说。
思路：让cur找比key指向的值小的，找到后，++prev，交换prev和cur位置的值。若cur比key指向的值大，则不交换。
prev和cur的关系：
1.cur还没遇到比key大的值时，prev紧跟着cur，一前一后。
2.cur遇到比key大的，prev和cur之间的一段都是最大的值
第一趟排序后的结果。这时候div为基准值。将左右子树分隔开。
全部排完序后的二叉树图。
3.代码递归图
红色线代表递归，绿色线代表返回。
4.代码实现
#include <stdio.h> void Swap(int* x, int* y) { int t = 0; t = *x; *x = *y; *y = t; } int PartSort(int* a, int left, int right) { int key = left; int prev = left; int cur = left + 1; //推荐写法一，较好理解 while (cur <= right) { if (a[cur] < a[key]) { ++prev; Swap(&a[cur], &a[prev]); } ++cur; } //写法二。比较妙，不好理解 //while (cur <= right) //{ // if (a[cur] < a[key] && a[++prev] != a[cur]) // { // Swap(&a[cur], &a[prev]); // } // ++cur; //} Swap(&a[prev], &a[key]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int div = PartSort(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } int main() { int arr[] = {6,3,2,1,5,4}; int sz = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, sz-1); return 0; }
到这里快速排序还没有完，因为它存在缺陷。还需继续优化。请往下看
四、三数取中优化(最终方案)
以上三种方法的时间复杂度
最好情况：是O(N*Log2N)。
最坏情况：也就是在数据有序的情况下，就退化为了冒泡排序 O(N2)
当给你一组上万个数据测试时，会发生超时现象。
例如LeetCode912. 排序数组
快排竟然超时了，这时候用三数取中来解决此问题。
1.三数取中
三数取中的含义：取三个数中间不是最大也不是最小的那个。
哪三个数？第一个，最后一个，和中间那个。
例如排以下数据时。
9 8 7 6 5 4 3 2 1 0
思路：
默认key选最左边的数。
1.三个数取第一个 9 和第二个 1 和中间的 5
2.选出不是最大也不是最小的那个，也就是5。
3.将5和key交换位置。也就是和最左边的数交换。
这样做可以打破单边树形状，可以使之变为二分。因为这时候5做了key，key的左边是比5小的，key的右边是比key大的。
二分后的时间复杂度还是N*LogN
注意：三数取中仍然无法完全解决
在某种特殊情况序列下时间复杂度变为O(n2)的情况
2.代码实现(最终代码)
int GetMidIndex(int* a, int left, int right) { //防溢出写法 //int mid = left + (right - left) / 2; 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 { if (a[mid] > a[right]) { return mid; } else if (a[right] > a[left]) { return left; } else { return right; } } } int PartSort(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[midi], &a[left]); int key = left; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[key]) { ++prev; Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[key]); return prev; } void QuickSort(int* a, int left, int right) { if (right <= left) return; int div = PartSort(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } int main() { int arr[] = { 6,1,2,7,9,3,4,5,10,8 }; int sz = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, sz-1); return 0; }
五、时间复杂度(重点)
结论大家都会，是N*LogN。
怎么算出来的呢？
1.最好情况下
在最好的情况下：每次选key刚好能平分这组数据，一直都是二分，构成了满二叉树。
1.对于单趟排序的一层递归，不管是哪种方法，left和right每次都遍历了一遍数组，时间复杂度为N。
2.因为满二叉树的高度为Log2N，所以递归深度(深度不等于次数)也为Log2N，所以递归Log2N层就是(N *Log2N).
3.综上所述，快排最好情况下时间复杂度为O(N * LogN).
2.最坏情况下
最坏情况下，每次选key都是最大或者最小的那个元素，这使得每次划分所得的子表中一个为空表，另一个表的长度为原表的长度-1.
这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法退化为冒泡排序，时间复杂度为N2
如图是给9 8 7 6 5 4 3 2 1排升序的例子。
每次选最左边的为key。
3.空间复杂度
在空间上来看，尽管快排只需要一个元素的辅助空间。
但是快排需要一个栈空间来实现递归
最好情况下：每一次都被均匀的分割为深度相近的两个子表，所需要栈的最大深度为Log2N。空间复杂度为O(Log2N)
最坏情况下：但最坏的情况下，栈的最大深度为n.这样快速排序的空间复杂度为O(N).这时就会导致栈溢出(Stack Overflow)。因为栈的空间很小。
这时候就需要非递归的算法，来解决栈溢出问题。
六、非递归写法
1.栈模拟递归快排
如图对以下数据排序
{ 6,1,2,7,9,3,4,5,10,8 }
void QuickSort(int* a, int begin, int end) { ST st; StackInit(&st); //先入0和9这段区间 StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { //接着出栈，9和0，注意后进先出 int end = StackTop(&st); StackPop(&st); int begin = StackTop(&st); StackPop(&st); //然后再进行对0和9这段区间单趟排序。 int keyi = PartSort(a, begin, end); //[begin , keyi - 1] [keyi+1,end] //最后判断区间是否为最小规模子问题，来判断是否需要继续入栈。 if (begin < keyi - 1) { StackPush(&st, begin); StackPush(&st, keyi - 1); } if (keyi + 1 < end) { StackPush(&st, keyi + 1); StackPush(&st, end); } } //记得销毁栈。 StackDestory(&st); }
由此可以看出，虽然栈实现快排不是递归，但是和递归的思想一样。简直和递归一模一样。
2.队列实现快排
废话不多说。看图
//快速排序的非递归形式1：通过队列来实现 void QuickSort(int* a, int begin, int end) { Queue q; QueueInit(&q); QueuePush(&q, begin); QueuePush(&q, end); while (!QueueEmpty(&q)) { int left = QueueFront(&q); QueuePop(&q); int right = QueueFront(&q); QueuePop(&q); int keyi = PartSort(a, left, end);//[left,keyi-1][keyi+1,right] if (left < keyi - 1) { QueuePush(&q, left); QueuePush(&q, keyi - 1); } if (keyi + 1 < right) { QueuePush(&q, keyi + 1); QueuePush(&q, right); } } QueueDestory(&q); }
浅浅总结下
快排的平均时间复杂度为O(N*LogN)
如果每次划分只有一半区间，另一半区间为空，则时间复杂度为n2
快排对初始顺序影响较大，假如数据有序时，其性能最差。对初始顺序比较敏感
