面試中的排序演算法（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"即可獲得，並實時更新！希望大家多多支持哦~
公眾號簡介：分享演算法工程師必備技能，談談那些有深度有意思的演算法，主要範圍：C++數據結構與演算法/深度學習（CV），立志成為Offer收割機！堅持分享演算法題目和解題思路（Day By Day)
推薦閱讀：
