[排序演算法] 快速排序 (C++) (含三種寫法)
- 2022 年 11 月 21 日
- 筆記
- Amαdeus的 [排序演算法] 合集
快速排序解釋
快速排序 Quick Sort 與歸併排序一樣，也是典型的分治法的應用。 (如果有對 歸併排序還不了解的童鞋，可以看看這裡喲~ 歸併排序)❤❤❤
快速排序的分治模式
1、選取基準值，獲取劃分位置。將原數組 a[l, r] 劃分為兩個子數組 a[l, mid – 1] 和 a[mid + 1, r]。在前一個數組中所有元素都小於等於 a[mid]，後一個數組中所有元素都大於等於 a[mid]。而此時的 a[mid] 的值就是我們所取的基準值，mid 就每次劃分的位置；
2、遞歸調用快速排序函數，分別對兩個子數組 a[l, mid – 1] 和 a[mid + 1, r] 排序；
3、快速排序我們是在原數組上進行操作的，所以我們並不需要合併，最後 a[l, r] 已經有序。
快速排序的三種寫法
快速排序比較普及的有三種寫法，分別是 左右指針法 挖坑法 和 前後指針法。主要是取得劃分位置實現的方法有所不同。
接下來會逐個介紹這三種快速排序的寫法。
左右指針法
左右指針法步驟
1、首先 我們一般選取最左邊的元素作為基準值 key。
2、然後我們需要定義兩個變數 i 和 j。
其中 i 為左指針(其實不是指針啦，只是為了方便這麼叫它😋)，初始 i = 0。 j 為右指針，初始 j = r – 1，向左遍歷不斷找到小於基準值 key 的元素。
3、我們先動右指針 j 向左遍歷直到找到小於當前基準值 key 的元素；然後我們再動左指針 i 向右遍歷直到找到大於當前基準值 key 的元素。
當 i 和 j 分別找到它們要找的元素時，我們需要將兩個元素進行位置交換。( 在這個過程中我們要保持 i < j )
4、重複步驟3，直到最後我們可愛的左右指針相遇，這時我們再將基準值 key，放到這兩個指針指向的位置。此時我們就得到了當前劃分的位置，基準值 key 也完成了歸位。
左右指針法移動指針先後順序問題
在上述步驟中，有些人會感到疑惑，那就是我們再移動指針時，每次都要 先移動右指針，再移動左指針。為什麼呢？😕😕😕
在取基準值時，我們一般都是將序列的最左邊位置的元素作為基準值。我們每次交換完元素後，左右指針都會繼續尋找他們要找的值，觀感上就是相互靠近。而問題就出在我們退出循環的那一刻。
我們一直保持 i < j，也就是說，我們會在 i == j 時退出循環。假設 在某次交換之後，此時 j 指向的是交換之後的一個大於基準值的元素，如果我們先動左指針 i 去尋找一個大於基準值的元素，然鵝還未找到就已經和右指針 j 相遇了，這個時候我們需要退出循環，交換基準值 key 到當前兩個指針指向的位置。
但是!!!，此時 i 和 j 指向的是大於基準值的元素，那麼我們進行交換基準值位置操作後，這個大於基準值的元素就被換到了序列的最左端，很明顯，這時候出現了非常非常非常嚴重的錯誤。
那如果我們先動右指針 j，去尋找一個小於基準值的元素，然鵝沒有找到就已經和左指針 i 相遇了，這個時候退出循環，i 和 j 指向的一定是一個小於等於基準值的值。
究其原因，這其實是我們取最左邊的元素作為基準值導致的。我們需要保證每次交換過來的元素是小於等於基準值的，所以我們先動右指針，再動左指針。
左右指針法動態演示
我們以序列 [3,14,6,1,2,17,7] 為例進行動態演示。(後面還會有先動左指針的錯誤演示)
左右指針法正確演示
左右指針法錯誤演示
左右指針法核心程式碼
//左右指針法
int Partition_Hoare(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小於基準值的值的下標
j--;
while(i < j && a[i] <= key) //向右找到大於基準值的值的下標
i++;
swap(a[i], a[j]);
}
/* i等於j時跳出循環 當前基準值此時在下標為i的位置(合適的位置) */
swap(a[left], a[i]); //最左邊的元素變為處於當前合適位置的元素,把基準值放在合適位置
return i; //返回合適位置(i,j都可以)
}
挖坑法
挖坑法步驟
挖坑法顧名思義，就是每次挖一個坑填入元素使其歸位。和左右指針法一樣，我們同樣需要兩個變數 i 和 j。
1、我們一般取最左邊的元素為基準值，然後在基準值處挖空(挖坑)
2、先動右指針 j 向左找到一個小於基準值的元素，然後將其填入先前挖的坑中，同時 j 指向的位置也多出來一個坑位。
3、再動左指針 i 向右找到一個大於基準值的元素，然後將其填入先前挖的坑中，同時 i 指向的位置又多出來一個坑位。
4、重複上述操作，直到最後兩個指針相遇，此時再在這個坑位上填入基準值，即完成了基準值的歸位，也就是我們劃分的位置。
(具體實現這個挖坑填坑的方式可以是元素值的覆蓋，也可以是元素交換的形式，在後面的核心程式碼中會給出這兩種方式)
挖坑法動態演示
我們以序列 [3,14,6,1,2,17,7] 為例進行動態演示。
圖(1)
圖(2)
挖坑法核心程式碼
//挖坑法1
int Partition_DigI(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //必須先動右邊的 因為取的基準值在左邊
j--; //向左尋找直到找到比基準值小的
a[i] = a[j]; //挖坑 填入比基準值小的值
while(i < j && a[i] <= key) //再動左邊的
i++; //向右尋找直到找到比基準值大的
a[j] = a[i]; //挖坑 填入比基準值大的值
}
/* i等於j時跳出循環 下標為i的位置即為合適的插入位置 */
a[i] = key; //在i,j相遇的地方填入基準值
return i;
}
//挖坑法2
int Partition_DigII(vector<int> &a, int left, int right){
int i = left; //從左邊開始
int j = right; //從右邊開始
int key = a[left]; //將最左邊的數設為基準值
while(i != j){
while(i < j && a[j] >= key) //必須先動右邊的 因為取的基準值在左邊
j--; //向左尋找直到找到比基準值小的
swap(a[i], a[j]); //交換
i++; //看下一個（可以省略）
while(i < j && a[i] <= key) //再動左邊的
i++; //向右尋找直到找到比基準值大的
swap(a[i], a[j]); //交換
j--; //看下一個（可以省略）
}
/* 一輪循環後基準值所在位置左邊的數都比基準值小,右邊的都比基準值大 */
/* i等於j時跳出循環 當前基準值此時在下標為i的位置(合適的位置) */
return i; //返回基準值合適位置
}
前後指針法
前後指針法步驟
前後指針法同樣需要兩個指針，一個是 pre，一個是 curr。pre 最後找到的是劃分後左半部分最後一個小於基準值的元素。
1、一開始我們一般將前指針 pre 指向待排序序列的第一個元素，後指針 curr 指向 pre 後面的一個元素。
2、然後我們讓 後指針 curr 去尋找小於當前基準值的元素，若找到這個元素，此時需要將這個小於基準值的元素和當前 前指針 pre 後一個的位置的元素進行交換，即與 pre + 1 位置的元素進行交換，同時前指針 pre 也往後移動一步。
3、在上述過程中我們需要保持 curr <= r，當 curr > r 退出循環時，需要將當前 pre 所指向的元素和基準值進行交換。最後返回這個pre，即為我們劃分的位置。
前後指針法動態演示
我們以序列 [3,14,6,1,2,17,7] 為例進行動態演示。
圖(1)
圖(2)
前後指針法核心程式碼
//前後指針法
int Partition_PreAndCurr(vector<int> &a, int left, int right){
int pre = left; //pre最後找到左半部分最後一個小於基準值的元素
int curr = pre + 1; //curr找到pre指向元素之後的下一個小於基準值的元素
int key = a[left];
while(curr <= right){
if(a[curr] < key && ++pre != curr) //當a[curr]>=key時pre保持不動,直到最後curr找到下一個小於基準值的元素
swap(a[curr], a[pre]); //pre往後移動到其下一個位置,並交換前後指針指向的元素
curr++;
}
swap(a[left], a[pre]); //最後將基準值和此時處於pre位置的小於基準值的元素交換
return pre;
}
快速排序時間複雜度
假設時間複雜度為 T(n)。在進行取得劃分位置上我們需要消耗 O(n) 的時間，在遞歸調用快速排序函數上，最好情況下如果每次我們取得的劃分位置為n/2的位置，即消耗了 2T(n/2) 的時間。最壞情況下如果每次我們取得的劃分位置為首或尾的位置，即消耗 T(n-1)+T(0)的時間。
故時間複雜度如下
最優時間複雜度
最壞時間複雜度
取基準值優化
如何高效取基準值
對於取基準值，我們發現 如果當前所取的基準值恰好是當前序列中最小的數或者最大的數，那麼我們的劃分位置必然是首或尾的位置，如果每次都這個亞籽，我們消耗的時間會非常的多，這顯然就是最壞情況下的時間複雜度的狀況。
那麼我們如何盡量地避免這件事呢？🤔🤔🤔
我們自然會想到隨機取數，這固然是一個很好的辦法，但是這個世界充滿了無限可能性。假如我們原先最左邊的元素並不是最小或最大的一個元素，但是隨機取到的元素卻恰好是那個最小或最大的元素呢？
(當然隨機取數這個方法也是值得嘗試的，後續程式中我不會用這個方式實現取基準值的優化，如果有需要，只需要把取基準值的幾行程式碼改成如下就可以了)
int random = rand() % (right - left + 1) + left;
swap(a[random], a[left]);
int key = a[left]
為了避免這種充滿戲劇性的情況，我們採取 三數取中 的方法取基準值。
三數取中，就是取序列中的最左邊，中間，以及最右邊三個數進行比較，以這三個數大小為中的元素作為基準值。這樣可以更大程度上避免劃分位置不好的情況，即使其並不能徹底避免，但是是一個很好的辦法。
取基準值優化核心程式碼
int GetMid(int a[], int left, int right){
int mid = (left + right)>>1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid為中間值
else
if(a[left] < a[right])
return right; //right為中間值
else
return left; //left為中間值
else
if(a[mid] > a[right])
return mid; //mid為中間值
else
if(a[left] > a[right])
return right; //right為中間值
else
return left; //left為中間值
}
完整程式源程式碼
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
/* 1 */
//左右指針法
int Partition_Hoare(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小於基準值的值的下標
j--;
while(i < j && a[i] <= key) //向右找到大於基準值的值的下標
i++;
swap(a[i], a[j]);
}
/* i等於j時跳出循環 當前基準值此時在下標為i的位置(合適的位置) */
swap(a[left], a[i]); //最左邊的元素變為處於當前合適位置的元素,把基準值放在合適位置
return i; //返回合適位置(i,j都可以)
}
/* 2 */
//挖坑法1
int Partition_DigI(vector<int> &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //必須先動右邊的 因為取的基準值在左邊
j--; //向左尋找直到找到比基準值小的
a[i] = a[j]; //挖坑 填入比基準值小的值
while(i < j && a[i] <= key) //再動左邊的
i++; //向右尋找直到找到比基準值大的
a[j] = a[i]; //挖坑 填入比基準值大的值
}
/* i等於j時跳出循環 下標為i的位置即為合適的插入位置 */
a[i] = key; //在i,j相遇的地方填入基準值
return i;
}
//挖坑法2
int Partition_DigII(vector<int> &a, int left, int right){
int i = left; //從左邊開始
int j = right; //從右邊開始
int key = a[left]; //將最左邊的數設為基準值
while(i != j){
while(i < j && a[j] >= key) //必須先動右邊的 因為取的基準值在左邊
j--; //向左尋找直到找到比基準值小的
swap(a[i], a[j]); //交換
i++; //看下一個（可以省略）
while(i < j && a[i] <= key) //再動左邊的
i++; //向右尋找直到找到比基準值大的
swap(a[i], a[j]); //交換
j--; //看下一個（可以省略）
}
/* 一輪循環後基準值所在位置左邊的數都比基準值小,右邊的都比基準值大 */
/* i等於j時跳出循環 當前基準值此時在下標為i的位置(合適的位置) */
return i; //返回基準值合適位置
}
/* 3 */
//前後指針法
int Partition_PreAndCurr(vector<int> &a, int left, int right){
int pre = left; //pre最後找到左半部分最後一個小於基準值的元素
int curr = pre + 1; //curr找到pre指向元素之後的下一個小於基準值的元素
int key = a[left];
while(curr <= right){
if(a[curr] < key && ++pre != curr) //當a[curr]>=key時pre保持不動
swap(a[curr], a[pre]); //pre往後移動到其下一個位置,並交換前後指針指向的元素
curr++;
}
swap(a[left], a[pre]); //最後將基準值和此時處於pre位置的小於基準值的元素交換
return pre;
}
/* 4 */
//取基準值的優化 三數取中
int GetMid(int a[], int left, int right){
int mid = (left + right)>>1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid為中間值
else
if(a[left] < a[right])
return right; //right為中間值
else
return left; //left為中間值
else
if(a[mid] > a[right])
return mid; //mid為中間值
else
if(a[left] > a[right])
return right; //right為中間值
else
return left; //left為中間值
}
//左右指針法 三數取中優化
int Partition_Better(vector<int> &a, int left, int right){
int pos = GetMid(a, left, right);
swap(a[pos], a[left]); //將取得的基準值和第一個位置交換
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key)
j--;
while(i < j && a[i] <= key)
i++;
swap(a[i], a[j]);
}
swap(a[i], a[left]);
return i;
}
/*******************************************************************/
void Quick_Sort(vector<int> &a, int left, int right){
if( left >= right )
return;
//int i = Partition_Hoare(a, left ,right); //分割 C(n) = n - 1
//int i = Partition_DigI(a, left, right);
//int i = Partition_DigII(a, left, right);
//int i = Partition_PreAndCurr(a, left, right);
int i = Partition_Better(a, left, right);
Quick_Sort(a, left, i - 1); //遞歸左邊的部分
Quick_Sort(a, i + 1, right); //遞歸右邊的部分
}
void show(vector<int> &v){
for(auto &x : v)
cout<<x<<" ";
cout<<endl;
}
main(){
vector<int> v;
srand((int)time(0));
int n = 50;
while(n--)
v.push_back(rand() % 100 + 1);
show(v);
Quick_Sort(v, 0, v.size() - 1);
cout<<endl<<endl;
show(v);
}
程式運行結果圖
