【数据结构初阶】排序算法(中)快速排序专题
文章目录
1. 快排主框架
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
简单地说，就是将数组分成左右两个部分，左部分都大于（或小于）中间的基准值，右部分都小于（或大于）中间的基准值，然后不断重复上述过程，直到数组完全有序。
//快排主框架voidQuickSort(int* a,int left,int right){if(left >= right)return;int mid =PartSort(a, left, right);QuickSort(a, left, mid -1);QuickSort(a, mid +1, right);}那么显然快排最关键的就是PartSort这个函数怎么实现了，这个函数要实现：找到基准值并将数据按照大小划分到基准值的两侧。
- 时间复杂度：
O(nlogn) - 空间复杂度：
O(logn)
2. 快排的不同实现
这里的PartSort函数的实现有很多种，这里介绍3种。
2. 1 hoare版本
算法思路
- 创建左右指针，确定基准值
- 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
- 跳出循环后，交换
right和key
提问1：为什么跳出循环后right位置的值一定不大于key?
当 left > right 时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key
提问2：当left==right时要不要跳出循环？
不能，因为此时不知道left和right同时指向的这个值的大小，必须让right或者left额外多走一步。
我们通过这三个场景来分析提问1并详细解释hoare版本的思路：
首先我们选定第一个元素为基准值（实际上选择基准值还有其他更好地方式，但这里先简化），然后将left=1，right=numsSize-1，也就是除了第一个元素外，数组的头和尾。
注：以升序为例。
场景一：left<key，left++；right > key，right不动。left++,left++,left指向7。left和right交换数据，数组变为：
int a[]={6,1,2,3,9,7};left++,right++,left==right,right指向9。
此时right大于key，肯定不能直接交换，必须再进行一次交换，让left > right，而因为此时right已经走到了left的左边，left的左边一定小于key。
将right与key交换，第一次快排结束，此时数组为：
int a[]={3,1,2,6,9,7};并将right返回，right就是基准值。
这里调用时，PartSort的返回值就是mid，left和right依然是传入的left和right，
QuickSort(a, left, mid -1);QuickSort(a, mid +1, right);接下来就是继续递归，left和right（在递归传参时改变）最终会在循环之前就left >= right，递归停止。
场景二：
第一次快排在交换right与key之前的结果是这样的：
int a[]={6,1,2,3,6,7};left与right相遇在6。
且此时left == right，right指向3。right位置的值不大于key。
场景三：
第一次快排在交换right与key之前的结果是这样的：left与right相遇在4。
int a[]={6,1,2,3,4,7};//实际上的步骤和场景二是一样的，只是right位置的值不一样且此时left == right，right指向3。right位置的值不大于key。
为什么不用left与right交换？
我们来看这个数组：
int a[]={6,1,2,3,7};left和right在7相遇，left++，right--之后，left指向的位置就已经越界了。
但是right就不会有这个问题，因为我们选中的基准值在最左边，即使在第二个数字相遇，right--之后也不会越界。
代码：
// 快速排序Hoare版本intPartSort1(int* a,int left,int right){int keyi = left;//设定key为最左边的值 left++;while(left <= right){while(left <= right && a[left]< a[keyi]) left++;while(left <= right && a[right]> a[keyi]) right--;if(left <= right)//注意这里要加这个判断，因为上面的两个循环可能是因为left>right结束的Swap(&a[left++],&a[right--]);}Swap(&a[right],&a[keyi]);//将right的值与keyi交换return right;}2. 2 挖坑法
思路：
创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标(即分界值下标)。
int a[]={6,1,2,7,9,3,4,5,10,8};我们以这个数组为例，分析挖坑法的步骤：
首先将6挖成坑，并将6存成key。
int hole = left;int key = a[left];先从右边开始遍历，到5时a[right] > key，停下遍历，将right的值放到坑中，并将right的位置挖成坑：
a[hole]= a[right];//把right的值放进坑中 hole = right;//把right挖成新的坑再从左边遍历，到7时，停下遍历，将left的值放到坑中，并将left的位置挖成坑。
重复上述过程，直到left > right，把最开始的key放进现在的坑中。
挖坑法实际上和hoare版本的原理差不多，只不过是挖坑填坑这个动作代替了交换，并没有本质的变化。
代码：
// 快速排序挖坑法intPartSort2(int* a,int left,int right){int hole = left;int key = a[left];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;//把key放进坑里return hole;//最后的坑就是基准值的位置}2. 3 lomuto前后指针法
创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
前指针prev在开始的时候指向left+1，后指针cur指向left也就是基准值。prev开始遍历，如果发现cur的值小于key，就把prev++，再cur和prev指向的值交换，当遍历完成后，把prev和left指向的值交换。这样结果就是比基准值小的值都会在prev的左边，那么比基准值大的值就会都在prev右边，划分就完成了。
我们以这个数组为例，简单说明一下前后指针法的步骤：
int a[]={6,1,2,7,9,3,4,5,10,8};一开始，prev指向6，cur指向1，key为6。cur向后遍历，发现2比6小，prev++，并与cur交换，但这是我们会发现prev和cur其实是一样的，那么交换就没有意义了，还会浪费性能，可以在这里添加一个判断。此时prev和cur都指向1。
然后cur继续遍历到2，和1一样。此时prev和cur都指向2。
接着cur继续遍历，直到cur指向3，prev++，然后与3进行交换，因为prev++之后指向的值是cur遍历过的，所以一定是大于key的。此时数组为：
int a[]={6,1,2,3,9,7,4,5,10,8};prev指向3，cur指向7。
…………
可以发现，在这个过程中比基准值小的值不断地被交换到prev及prev的左边，那么最终把基准值与prev交换，就可以实现划分了。
// 快速排序前后指针法intPartSort3(int* a,int left,int right){int prev = left;int cur = left +1;int key = a[left];while(cur <= right){if(a[cur]< key &&++prev != cur)//先++，再比较Swap(&a[cur],&a[prev]);//Swap函数自行实现即可 cur++;}Swap(&a[left],&a[prev]);//把基准值放到prev的位置return prev;}2. 4 快排的非递归版本
上面的三种方法都是通过递归实现的，那么有没有办法不使用递归实现快速排序呢？
当然有，只不过需要借助数据结构——栈。
用left和right进行基准值的计算并划分，然后把本应递归的区间的新的left和right入栈，在入栈或出栈时判断left和right的大小是否合适，一直运行到栈为空，快速排序就完成了。
voidQuickSortNonR(int* a,int left,int right){ Stack st;StackInit(&st); Stack* tmp =&st;//以上均为创建栈StackPush(tmp, right);//将初始的left和right入栈，可以方便StackPush(tmp, left);while(!StackEmpty(tmp)){//出栈得到本次循环的left和rightint lefti =StackTop(tmp);StackPop(tmp);int righti =StackTop(tmp);StackPop(tmp);//采用前后指针法得到基准值并划分，也可以使用其他的办法int keyi = lefti;int prev = lefti;int cur = lefti +1;while(cur <= righti){if(a[cur]< a[keyi]&& prev++!= cur)Swap(&a[cur],&a[prev]); cur++;}Swap(&a[prev],&a[keyi]); keyi = prev;//入栈前判断if(keyi -1> lefti){StackPush(tmp, keyi -1);StackPush(tmp, lefti);}if(keyi +1< righti){StackPush(tmp, righti);StackPush(tmp, keyi +1);}}//销毁栈StackDestroy(tmp);}3. 快排优化
3. 1 快排性能的关键点分析:
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本二分居中，那么快排的递归树就是颗均匀的满二叉树，性能最佳。但是实践中虽然不可能每次都是二分居中，但是性能也还是可控的。但是如果出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组序列有序时就会出现这样的问题，我们可以用三数取中（选取3个数，把大小在中间那个作为基准值）或者随机选key（使用随机数选基准值，这两种办法实际的效率提升不是很高，不单独介绍了）解决这个问题，但是现在还是有一些场景没解决，比如数组中有大量重复数据时，比如以下代码：
// 数组中有多个跟key相等的值int a[]={6,1,7,6,6,6,4,9};int a[]={3,2,3,3,3,3,2,3};// 数组中全是相同的值int a[]={2,2,2,2,2,2,2,2};这种时候快排的效率就会急剧下降，完全不如其他的较快的排序算法（如堆排序）。
3. 1 三路划分
当面对有大量跟key相同的值时，三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段【比key小的值】【跟key相等的值】【比key大的值】，所以叫做三路划分算法。结合步骤，理解一下实现思想：
key默认取left位置的值。left指向区间最左边，right指向区间最后边，cur指向left+1位置。cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++。cur遇到比key大的值后跟right位置交换，换到右边，right--。cur遇到跟key相等的值后，cur++。- 直到
cur > right结束
int a[]={6,1,7,6,6,6,4,9};//前int a[]={1,4,6,6,6,6,9,7};//后int b[]={6,6,6,6,6,6,6,6};//前int b[]={6,6,6,6,6,6,6,6};//后代码：
voidQuickSortTreeWay(int* a,int left,int right){if(left >= right)return;int begin = left;int cur = left +1;int end = right;int key = a[left];while(cur <= right){if(a[cur]> key){//把大于key的数放到右边Swap(&a[cur],&a[end--]);//注意由于不确定被换过来的值的大小，cur不能直接++}elseif(a[cur]== key){ cur++;//等于key的先不管}else{Swap(&a[cur++],&a[begin++]);//小于key的放到begin的左边}}//递归时，begin-end的数不需要再调整QuickSortTreeWay(a, left, begin -1);QuickSortTreeWay(a, end +1, right);}3. 2 introsort自省排序
introsort是由David Musser在1997年设计的排序算法，C++ sgi STLsort中就是用的introspectivesort(内省排序)思想实现的。
内省排序可以认为不受数据分布的影响，无论什么原因划分不均匀导致递归深度太深，它都会转换为堆排painkiller，而堆排不受数据分布影响，具体可以看下面代码。
三路划分针对有大量重复数据时效率很好，其他场景就一般，而自省排序在任何场景都有优异的性能。
introsort是introspective sort采用了缩写，他的名字其实表达了它的实现思路，也就是进行自我侦测和反省，快排递归深度太深(sgi stl中使用的是深度为2倍排序元素数量的对数值)那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。
voidIntroSort(int* a,int left,int right,int depth,int defaultDepth){if(left >= right)return;// 数组⻓度小于16的小数组，换为插入排序，简单递归次数if(right - left +1<16){InsertSort(a + left, right - left +1);return;}// 当深度超过2*logN时改⽤堆排序if(depth > defaultDepth){HeapSort(a + left, right - left +1);return;} depth++;//深度++,方便判断int begin = left;int end = right;// 随机选key,相较于直接将第一个元素作为key，有一定的优势int randi = left +(rand()%(right - left +1));Swap(&a[left],&a[randi]);//把选中的key放到left上，和之前的快排尽可能保持相似//前后指针法int prev = left;int cur = prev +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;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi -1, depth, defaultDepth);IntroSort(a, keyi +1, end, depth, defaultDepth);}voidQuickSort(int* a,int left,int right){int depth =0;int logn =0;int N = right - left +1;//计算lognfor(int i =1; i < N; i *=2){ logn++;}// introspective sort -- 自省排序IntroSort(a, left, right, depth, logn *2);}int*sortArray(int* nums,int numsSize,int* returnSize){srand(time(0));QuickSort(nums,0, numsSize -1);*returnSize = numsSize;return nums;}谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章
