面试中的排序算法（Part 2）
今天我们介绍两个复杂点的排序算法随机快排和希尔排序，这也是面试的重点，考察范围包括代码书写，复杂度分析以及稳定性比较！好吧，让我们开始今天的算法之旅吧！
荷兰国旗问题
在说随机快排之前，我们首先要谈一下荷兰国旗问题，这个方法的一个重要拓展就是快排问题！
我们把荷兰国旗问题用数组的形式表达一下是这样的： 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。
比如，给定一个数组[2, 3, 1, 9, 7, 6, 1, 4, 5]，再给定一个数6，那么变换之后的数组可能就是[2, 3, 1, 1, 4, 5, 6, 7, 9]。然后返回等于6这个数区间范围！！！也就是返回结果[6, 6]。
具体的算法原理是： 首先我们定义两个范围指针分别是less和more，以及一个当前指针cur，其中，less指针指向-1的位置，more指针指向N+1的位置。然后我们使用cur指针对整个数据进行依次遍历，遍历终止的条件是cur指针和more指针指向同一区域！在遍历的过程中有以下三种情况：
- 当cur指向数值小于num时，less指针向后移
- 当cur指向数值大于num时，more指针向前移
- 当cur指向数值等于num时，less和more不动，cur向后遍历
这样最后就可以将数组分成两个部分，一部分小于num，另一部分大于num，返回值我们返回less+1以及more，也就是等于num的索引部分（左闭右开）！
// 荷兰国旗问题：将数组按照num分成两份，左边小于num，右边大于num
vector<int> qs_partition(vector<int>& list, int L, int R, int num) {
int less = L - 1;
int more = R + 1;
int cur = L;
vector<int> res;
while (cur < more) {
if (list[cur] < num)
swap(list[++less], list[cur++]);
else if (list[cur] > num)
swap(list[--more], list[cur]);
else {
cur++;
}
}
res.push_back(less + 1);
res.push_back(more);
return res;
}(随机)快排
快排的方式有很多中，也有很多种优化方式，这里我们只说经典的快排方式，以及他的改进版本——随机快排！
快排（Quick Sort）核心思想就是使用分而治之的方法，递归的对序列使用荷兰国旗问题的排序方法。
经典快排结构图 首先将分割数组的num设置为最右边的数，进行qs_partition，将数组分割成两个部分后，由于这两个部分是无序的，就递归地进行QuickSort，递归退出的条件是分割后部分的size为1或者是空！具体的流程可以看上图！
那么我们这个算法是最好的么？为什么我们要认定一开始以最后一个数为分割数呢，如果每次分割最后一个数都恰好在中间的位置，那么我们就有可能需要全部进行交换了！因此随机快排就是相比经典快排多了一步，设置随机数，选择随机的初始分割位置！
为了方便编程，我们整体的程序设计结构没有变化，还是以最后一个数开始，只不过我们在开始之前会随机选择一个值和最后一个数进行交换，这样就达到了我们的目的，每次调用函数初始分割数都随机，这样可以达到理论上的O(NlogN)的复杂度～
// 迭代一次返回中间等于num的数，是一个区间，num首次应该是list[R]
vector<int> qs_partition(vector<int>& list, int L, int R) {
int less = L - 1;
int more = R; // 最后一个数list[R]不参与遍历，省一个变量
int cur = L;
vector<int> res(2);
while (cur < more) {
if (list[cur] < list[R])
swap(list[++less], list[cur++]); // L相当于索引
else if (list[cur] > list[R])
swap(list[--more], list[cur]);
else {
cur++;
}
}
swap(list[more], list[R]);
res[0] = cur;
res[1] = more;
return res;
}
// 五、(随机)快速排序算法（如果产生数的范围较小，那么快排速度很慢，说明快排和数据的状况是有关系的）
void QuickSort(vector<int>& list, int L, int R) {
default_random_engine e; # 在random头文件中，随机数发生器
if (list.size() < 2) {
return;
}
if (L < R) {
swap(list[L + e() % (R - L + 1)], list[R]); // 随机快排的空间复杂度为O(logn)
vector<int> p = qs_partition(list, L, R);
QuickSort(list, L, p[0] - 1);
QuickSort(list, p[1] + 1, R);
}
}希尔排序
希尔排序结构图 在学习希尔排序之前，希望你们都可以去看一下上一篇文章的简单插入排序，也叫直接插入排序，希尔排序的核心是：将一个数组首先分成几个子序列(步长大时，子序列元素少，但索引间隔大，更无序性，反之，元素多，索引间隔小，更有序性)，然后对每个子序列进行直接插入排序，大家就会有疑问？这就不是明显的插入排序，怎么就高效了？
对，最重要的是步长的概念，一开始步长一半选为整个数组长的一半，然后二倍的下降，如果最小的元素在数组的末尾，由于步长的概念，也会很快的移到前面去（子序列元素很少，但位置相差一开始很大），对于简单插入排序，你就不得不对整个序列两两排序！
void ShellSort(vector<int>& list){
int len = list.size();
int gap = len / 2;
int i, j;
while(gap >= 1){ // 按照gap拆分序列，gap每次减小一半
for(i = gap;i < len;i++){
j = i; // 对拆分后的子序列进行插入排序
while(j >= gap && list[j-gap] > list[j]){
swap(list[j-gap], list[j]);
j -= gap;
}
}
gap /= 2;
}
}复杂度分析
复杂度总结 这里主要说一下随机快排和希尔排序的复杂度，我们可以看到随机快排需要O(nlogn)的空间，这是因为每次二分时都要保存与分割数相等的区间的左右端点！由于二分的话，需要O(nlogn)的空间复杂度。很奇怪，从理论上来说希尔排序应该综合性能最好的，但是在实际应用当中，特别是大数据的时候，综合看来，快排的效率还是最高的！
资源分享
完整测试文件（C++版）,文件名为：常见排序算法（重点），请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~
腾讯云开发者
