【数据结构初阶】排序算法(中)快速排序专题
1. 快排主框架
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
简单地说，就是将数组分成左右两个部分，左部分都大于（或小于）中间的基准值，右部分都小于（或大于）中间的基准值，然后不断重复上述过程，直到数组完全有序。
//快排主框架
void QuickSort(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版本
int PartSort1(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版本的原理差不多，只不过是挖坑填坑这个动作代替了交换，并没有本质的变化。
代码：
// 快速排序挖坑法
int PartSort2(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交换，就可以实现划分了。
// 快速排序前后指针法
int PartSort3(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的大小是否合适，一直运行到栈为空，快速排序就完成了。
void QuickSortNonR(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和right
int 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}; //后代码：
void QuickSortTreeWay(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不能直接++
}
else if (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出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。
void IntroSort(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);
}
void QuickSort(int* a, int left, int right)
{
int depth = 0;
int logn = 0;
int N = right - left + 1;
//计算logn
for (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;
}谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！ 我会持续更新更多优质文章
腾讯云开发者
