【数据结构初阶】排序算法(中)快速排序专题

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这个函数怎么实现了，这个函数要实现：找到基准值并将数据按照大小划分到基准值的两侧。

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)

2. 快排的不同实现

这里的PartSort函数的实现有很多种，这里介绍3种。

2. 1 hoare版本

算法思路

1. 创建左右指针，确定基准值
2. 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
3. 跳出循环后，交换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和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大的值】，所以叫做三路划分算法。结合步骤，理解一下实现思想：

1. key默认取left位置的值。
2. left指向区间最左边，right指向区间最后边，cur指向left+1位置。
3. cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++。
4. cur遇到比key大的值后跟right位置交换，换到右边，right--。
5. cur遇到跟key相等的值后，cur++。
6. 直到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;//计算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;
}

谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章