数据结构——lesson11排序之快速排序
前面我们学习过五种排序——直接插入排序、希尔排序、直接选择排序、堆排序和冒泡排序，今天我们就来学习交换排序的第二种——快速排序。
1.快速排序（递归版）
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复（这里使用递归来重复，非递归版本将在后续讲解）该过程，直到所有元素都排列在相应位置上为止。
那怎么实现左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值呢？ 下面将介绍三个方法实现，分别是Hoare版本实现、挖坑法和前后指针法；
1.1Hoare版本实现
①选定一个基准值key（假设每次都为最左边的数），定义左右下标left，right； ②right先走从右往左找到小于key的值停在那里； ③左边再开始从左往右走直到停在大于key的值上，然后交换左右两个值； ④接着右边继续往左走继续找小于key的值，找到后左边往右走找大于key的值； ⑤直到左右left和right相遇，也就是left = right，此时该位置的值一定小于key（等学完Hoare后再来分析），再将该值与key交换即可； 🥳🥳这样key左边都是小于它的，右边都是大于它的，在整个序列中的位置就确定好了，接下来我们按照上述方法分别实现key左边的序列和右边的序列有序即可； 图示如下：
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
if (left >= right)//如果left一开始就小于right就不需要继续往下了
return 0;
int keyi = left;
int key = a[left];
while (left < right)
{
//right先走
while(left < right && a[right] < key )
{
if (a[left] > key)
{
Swap(&a[left], &a[right]);
break;
}
left++;
}
right--;
}
//当left=right时此时一定a[left] < a[keyi],要交换
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)//递归结束条件
return;
int keyi = PartSort1(a, left, right);
QuickSort(a, left, keyi-1);//递归左右序列
QuickSort(a, keyi+1, right);
}结果如下：
这里注意第二层while循环时也要讲条件left<right写上去，可以防止越界：当right首次向左走时如果没有一直遇到小于key的值那么right就有可能越界；
交换函数在这里🥳🥳
//交换函数
void Swap(int* a, int* b)
{
int tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}注意传指针才可以改变参数的值哦~
现在我们来分析为什么left = right时，该位置的值一定小于key 原因如下： 我们在看代码时发现是right先走，这肯定是有它的用意的 left与right相遇无非两种情况： ✨✨（1）left与right相遇：因为是right先走，所以left与right相遇，right此时肯定走过一次，right应该停在小于key的位置上，当left与right相遇时，此时该位置的值小于key ✨✨（2）right与left相遇：同样因为right先走，所以right与left相遇无非两种情况： 🧨🧨🧨①left一次都没走：此时right直接走到最左边，都不用管该位置值直接就是key，交换也没有影响所以可以不考虑； 🧨🧨🧨 ②left走了，那么当right走到与left相遇时，left的值是上次交换后小于key的值，所以相遇时该位置的值小于right;
所以如果将左边定位基准值key那么要让right先走：保障了相遇位置比key小； 依此类推：如果将右边定位基准值key，那么要让left先走：保障了相遇位置比key大；
1.2挖坑法实现
挖坑法较Hoare版本好理解： ①它先需要确定一个坑位hole和基准值key来存放坑位原来的值； ②左右下标也要有left和right，如果以左边的值为基准就要从右边先开始往左找到比key小的数填到坑位里，然后右边的就成为新的坑位； （当然如果以右边的值为基准就要从左边开始往右找大于key的数） ③左边再开始找大于key的数，找到后填到新的坑位里，左边就成了新的坑位； ④依次循环直到left与right相遇跳出循环； 图示如下：
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int hole = left;
int key = a[hole];
while (left < right)
{
//右边找小
while (left < right && a[right] >= key)
{
right--;
}
//填坑
a[hole] = a[right];
hole = right;//新坑
//左边找大
while (left < right && a[left] <= key)
{
left++;
}
//填新坑
a[hole] = a[left];
hole = left;
}
//结束时坑位左边都比它小，右边都比它大
a[hole] = key;
return hole;
}
//递归实现
void QuickSort(int* a, int left, int right)
{
if (left >= right)//递归结束条件
return;
int keyi = PartSort2(a, left, right);
QuickSort(a, left, keyi-1);//递归调用左边
QuickSort(a, keyi+1, right);//递归调用右边
}注意✨✨： ①这里嵌套的while循环中也要写条件——left<right不然就会和Hoare版本一样出现越界访问； ②此外另外一个条件a[right] >= key，a[left] <= key不要漏掉等于号不然当左右两边都存在等于key的数时就会出现死循环哦~
结果如下：
1.3前后指针法实现💥
（1）前后指针法首先要定义指向数组的前后两个下标——prev和cur（注意这里的指针说的是下标），同时也需要基准值key（这里依然定义为最左边的数）； （2）这里的循环条件不太好实现： ✨①在没遇到小于key的值之前cur和prev一直向前； ✨②在遇到第一个大于key的值后，prev不再向前，因为prev开始时就时cur的前一位，所以此时prev的下一个就是第一个大于key的值； ✨③与此同时cur继续向前不做停顿，直到cur遇到小于key的值停下与++prev交换，这样一来之前遇到的大的值就被cur指向的小的值交换了，大的就到了后面； ✨④依此类推cur继续向后寻找小于key的值，prev同样不需要再向前，cur找到后与++prev交换…直到cur>right跳出循环； （3）结束循环后prev的位置就是key合适的位置，交换两个位置的值并返回该位置的下标； （4）然后再利用递归来实现完整序列的排序即可🥳🥳 图示如下：
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int key = a[left];
int cur = left+1;
int prev = left;
while (cur <= right)
{
//如果a[cur]<=key并且++prev的值不等于cur时说明prev与cur之间有大于key的值就需要交换了
//如果a[cur]<=key并且++prev的值等于cur时说明此时还没出现大于key的值cur和prev继续向前
//如果a[cur]>key说明出现了大的值，此时只要cur向前走就行，直到遇到下一个小值与++prev交换
if (a[cur] <= key && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[left]);
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);//递归调用右边
}结果如下： 如下图递归完一次之后int a[] = { 8,4,6,9,1,3,5,0,7,2 };最左边的数8找到了它最合适的位置——倒数第二位🥳🥳
排完序结果如下：
2.快速排序（非递归版）
快速排序的递归调用虽然能够解决问题，但是递归调用的是栈帧，是在栈上实现的，但是栈的空间一般只有8MB，如果递归很深的话有可能造成栈溢出的风险，所以我们也需要学习和掌握快速排序非递归版本；
要实现快速排序的非递归版本我们就可以用之前学习过的栈来模拟实现递归（当然使用队列也可以），详解在这里：数据结构——lesson5栈和队列；我们接下来将用到之前写过的栈来实现快速排序；
①我们利用栈先进后出的特点将左右子序列按照左右下标入栈的方式来标记，每次取出栈顶的元素当作左右下标； ②利用前面实现的三种方法任意一种来对序列进行排序； ③排好后获得key正确位置的下标keyi，并由keyi分割出两个左右子序列； ④并将两个序列的左右下标都入栈，等到下一次排序时调用； ⑤直到keyi无法分割时就不再继续入栈； ⑥直到栈空，排序也就完成🥳🥳
#include"stack.h"
void QuickSortNR(int* a,int left,int right)
{
//定义和初始化栈
Stack ST;
StackInit(&ST);
//将整个序列入栈
StackPush(&ST, right);
StackPush(&ST, left);
//当栈不为空时
while (!StackEmpty(&ST))
{
//取栈顶的两个元素作为左右下标
int left = StackTop(&ST);
StackPop(&ST);
int right = StackTop(&ST);
StackPop(&ST);
//利用前面讲过的三种方法任意一种来对取出的左右下标组成的序列排序
int keyi = PartSort1(a, left, right);
//如果能够分割左右序列就让它们入栈
if (keyi + 1 < right)
{
//记得入栈顺序不能随意，因为栈是先进后出有顺序要求
StackPush(&ST, right);
StackPush(&ST, keyi + 1);
}
if(left < keyi-1)
{
//这里入栈顺序也要注意顺序
StackPush(&ST, keyi - 1);
StackPush(&ST, left);
}
}
//销毁栈
StackDestroy(&ST);
}
int main()
{
int a[] = { 8,4,6,9,1,3,5,0,7,2 };
//Swap(&a[0], &a[1]);
QuickSortNR(a,0,9);
return 0;
}结果如下：
3.快速排序（改良版）
我们发现如果序列在接近有序的情况下，快速排序都会非常的慢，因为我们每次PartSort取得都是最左边的元素作为基准值key，如果在接近有序的情况下要遍历N遍数组,数组序列每次-1，类似于等差数列，效率太低；如下图所示：
此时时间复杂度为O(N^2); 🥳🥳所以我们可以选择一个不那么大或者不那么小的元素作为基准值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;
}
}
}获得中间值的下标后直接与最左边的数交换即可（以Hoare版本为例）：
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
if (left >= right)//如果left一开始就小于right就不需要继续往下了
return 0;
int midi = GetMidIndex(a,left,right);
//与left的值交换即可，其他不变
Swap(&a[left],&a[midi]);
int keyi = left;
int key = a[left];
while (left < right)
{
//right先走
while(left < right && a[right] < key )
{
if (a[left] > key)
{
Swap(&a[left], &a[right]);
break;
}
left++;
}
right--;
}
//当left=right时此时一定a[left] < a[keyi],要交换
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)//递归结束条件
return;
int keyi = PartSort1(a, left, right);
QuickSort(a, left, keyi-1);//递归左右序列
QuickSort(a, keyi+1, right);
}其他两种方法和上述一致🥳🥳🥳
4.快速排序复杂度分析
4.1快速排序空间复杂度
无论时递归还是非递归实现，调用的空间都是O(logN)，递归实现要调用栈帧，左右子序列，类似于二分，左序列再调用左右序列…，并且空间是可以复用的，左边归还之后调用右边序列则可以重复使用，所以调用的空间是logN(以2为底)； 非递归实现使用了栈，与递归过程类似；
4.2快速排序时间复杂度
快排改良版的时间复杂度是：O(NlogN)
此时不需要遍历N遍，只需要logN层即可遍历完，每层都是N次，所以是O(NlogN)；
5.结语
以上就是快速排序的所有内容啦~我们共使用了递归版的三种方法以及非递归版来实现快速排序，并改良了快速排序，分析了它的时间和空间复杂度，完结撒花 ~🥳🥳🎉🎉🎉