【排序算法】快速排序（全坤式超詳解）——

【排序算法】——快速排序

一：快速排序——思想

二：快速排序——分析

三：快速排序——動態演示圖

四：快速排序——單趟排序

4.1：霍爾法

4.2：挖坑法

4.3：前后指針法

五：快速排序——遞歸實現

5.1：快速排序--->常規法

5.2：快速排序--->三路劃分法

六：快速排序——非遞歸實現

七：快速排序——優化

7.1：快速排序優化--->三數取中選key法

7.2：快速排序優化--->隨機數生成選key法

7.3：快速排序優化--->小區間改造

八：快速排序——特性總結

一：快速排序——思想與大致框架

????????快速排序是Hoare（霍爾）于1962年提出的一種二叉樹結構的交換排序方法。

其基本思想為：

任取待排序元素序列中的某元素作為基準值，
按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，
然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

?由快排思想可以推出快速排序的大致框架如下：

#include <stdio.h>// 假設按照升序對array數組中[begin, end]區間中的元素進行排序void QuickSort(int array[], int begin, int end) 
{if (begin >= end){return;}// 按照基準值對array數組的 [begin, end]區間中的元素進行劃分int keyi = PartSort(array, begin, end);// 劃分成功后以keyi為邊界形成了左右兩部分 [begin, keyi-1] keyi [div+1, end]// 左部分都是比 keyi 位置上的值小的部分，右部分都是比 keyi 位置上的值大的部分。// 遞歸排左部分[begin, keyi-1]QuickSort(array, begin, keyi);// 遞歸排右部分[keyi+1, end]QuickSort(array, keyi+1, end);}int main()
{int a[] = { 2,5,7,1,4,9,6,3,8,0 };int sz = sizeof(a) / sizeof(a[0]);    // 求取數組內元素個數QuickSort(a, 0,sz-1);                // 傳遞的都是下標return 0;
}

????????我們發現與二叉樹前序遍歷規則非常像，所以我們在分析快速排序過程中的遞歸框架時可想想二叉樹前序遍歷規則即可理解并快速寫出來，在后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。?

二：快速排序——分析

? ? ? ? 對于快速排序，重點就在于基準值 key 的位置，知道 key 的位置之后，分別再對左右兩邊部分再找基準值 key 的位置，依次在各個部分區間內找基準值 key，通過一遍又一遍的遞歸，到最后區間內只有一個數時，這個遞歸也就結束了。具體情況，大家可以通過快速排序的動態演示圖和遞歸分解圖進行分析。

三：快速排序——動態演示圖

快速排序遞歸演示圖：

我們發現它大致就是一個二叉樹的前序遍歷形態。大家可以一邊看圖一邊進行分析。?

四：*快速排序——單趟排序**

將區間按照基準值劃分為左右兩半部分的常見方式有：1.霍爾法；2.挖坑法；3.前后指針法

4.1：霍爾法

????????因為霍爾是最早實現快速排序的人，所以霍爾法也是整個快排最早的版本。

單趟排序的目的：將區間按照基準值劃分為左右兩半部分，左邊部分比基準值小，右邊部分比基準值大。

?霍爾法單趟過程分析：

先記錄下基準值key的位置，讓?left 和 right 向兩端靠近（直至相遇）。
right 小兵先走，直到遇到一個比 key 值要小的數字就停下。
right 小兵停下后，left 小兵再走，直到遇到一個比 key 值要大的數字就停下。
交換 left 位置和 right 位置上的值。
right 小兵繼續走，重復 2，3，4動作，直到 left 小兵與 right 小兵相遇
相遇之后，將相遇位置的值與基準值 key 位置上的值交換，讓相遇位置置成新的 key。

注意：基準值 key 在左邊， right 小兵先走；基準值 key 在右邊，left 小兵先走。

那么，相信大家會有這樣的疑問，如果相遇位置的值比基準值 key 位置上的值大怎么辦？無需擔心，相遇位置的值一定就是比基準值 key 位置上的值小。

這需要兩個方面進行分析：一方面是 key 在左邊，另一方面就是 key 在右邊。

key 位置在左邊

就相遇位置值分析：

若 left 小兵與 right 小兵相遇，又有兩種情況：1. left 小兵走的時候，遇到 right?小兵（L遇）；2.right 小兵走的時候，遇到 left 小兵（R遇L）。

1. left 小兵走的時候，遇到 right?小兵

?因為是 key 位置在左邊， right 小兵先走，所以當 right 小兵停下時，其位置上的值一定是比 key 位置上的值小的。這時，left 小兵來了，兩個小兵相遇，相遇的位置就是 right 小兵停下的位置，即相遇的位置比 key 位置上的值要小。

2. right 小兵走的時候，遇到 left?小兵

因為是 key 位置在左邊， right 小兵先走。經過幾輪交換之后，相遇的位置就是 left 小兵的位置，此時，因為經過了上一輪 left 位置上的值與 right 位置上的值交換。left 位置上的值就是上一輪交換中 right 停下位置上那個比 key 值小的值。即交換之后 left 位置上的值是比 key 位置上的值要小的，所以相遇的位置比 key 位置上的值要小。

同理，key 位置在右邊的時候，也是相同的情況分析。

下面我們來看一看 hoare 版本的代碼，一起來分析一下。

// 單趟排序
//		1.霍爾法
int PartSort1(int* a, int left, int right)
{int keyi = left;                // 記錄下 key 的位置while (left < right)            // 當 left 與 right 相遇時退出循環{// 右邊找小while (left < right && a[right] >= a[keyi]){--right;}// 左邊找大while (left < right && a[left] <= a[keyi]){++left;}// 此時 right 位置上的值要比 keyi 位置上的值小，left 位置上的值要比 keyi 位置上的值大// 交換 left 位置與 right 位置上的值。Swap(&a[left], &a[right]);      // 交換后 left 位置上的值比 keyi位置上的值小， right 位置上的值比 keyi 位置上的值大。}// left 與 right 相遇Swap(&a[left], &a[keyi]);keyi = left;            // 生成新的 keyi 位置return keyi;
}// 霍爾單趟排序之后， keyi 位置左邊的部分都比 keyi位置的值要小，keyi 位置右邊的部分都比 keyi位置的值要大。

4.2：挖坑法

挖坑法的思路與霍爾法的思路大致相同。

挖坑法思路過程分析：

先將 key 的值存起來，注意：此處的 key 存的是值，而不是位置下標。將該數據位置看作是一個坑（記作是 hole ）。
最初時，left 小兵在最左邊（下標為0的位置），right 小兵在最右邊。
如下動圖中，因為 hole坑在最左邊，所以還是 right 小兵先走，找比 key值要小的值。找到之后，將 right 位置上的值放到原來的坑上，在將此時 right 位置記作新坑。
right 位置上形成一個新坑后，left 小兵出發，找比 key 值要大的值。找到之后，將 left 位置上的值放到原來的坑上，在將此時 left 位置記作新坑。
left 位置上形成新坑后，right 小兵再走，重復3，4動作，直到 left 小兵與 right 小兵相遇。
相遇之后，將坑上填入 key 值。
最后返回 hole 最后的位置，這個位置就是基準值。

可以確定：兩個小兵相遇的位置一定是一個坑。

注意：有坑的小兵不走；填坑時，要先將原來的坑給補上，再建立新坑。

?單趟排序挖坑法代碼實現：

// 2.挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];            // 將基準值存起來int hole = 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;        // 最后一個坑填 基準值 keyreturn hole;          // 返回基準值的下標
}

4.3：前后指針法

這三種單趟排序的方法思想都是差不多的。不過這種方法不僅是思路還是實現效率都比其他兩中方法要好一些，同時這種方法也是大眾比較流行的方法之一。

前后指針法思路過程分析：

先記錄下基準值key的位置，不過這種方法不是 right 小兵和 left 小兵往中間走了，而是先用一個 “指針prev” 記錄left 的位置，再用一個 “指針cur” 記錄 left+1 的位置。
此時 cur 小兵要找比 key 位置上的值要小的，找到之后，并且 prev+1 != cur，就讓 prev+1 的位置上的值與 cur 位置上的值進行交換。
交換后 cur++，prev++。
依次重復2，3直至結束循環（cur > right）
最后將 prev 位置上的值與 key 位置上的值進行交換。再 key = prev。
返回 key 位置的下標

??單趟排序前后指針法代碼實現：

// 3.前后指針法
int PartSort3(int* a, int left, int right)
{int prev = left;            // 定義一個 prev “指針”int cur = left + 1;         // 定義一個 cur “指針”int keyi = left;            // 先確定基準值的位置while (cur <= right){while (a[cur] <= a[keyi] && ++prev != cur)    // cur指針找小，并且 prev先+1，加1之后再進行交換（簡化代碼）{Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);        // 交換 key 位置上的值與 prev 位置上的值keyi = prev;return keyi;
}

五：快速排序——遞歸實現

5.1：快速排序--->常規法

所謂常規法，就是按照我們前面的思路對快速排序進行總結實現，無任何添加，即是常規。

#include<stdio.h>// 快排單趟排序
//        前后指針法
int PartSort(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){while (a[cur] <= a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}// 快排遞歸實現
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort(a, begin, end);// [beign,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}// 快速排序
int main()
{int a[] = { 2,5,7,1,4,9,6,3,8,0 };int sz = sizeof(a) / sizeof(a[0]);QuickSort(a, 0,sz-1);return 0;
}

5.2：快速排序--->三路劃分法

萬事總有漏洞，但總會有大佬來填補這些漏洞。

當一個數組序列中含有多個相同元素的時候，單純的使用常規法已經不能發揮出獨屬于快排的全部威力了。這就有大佬提出了三路劃分法來解決這一問題。

圖：

以下個數組序列為例：

此處：L 指的是 left，c 指的是 cur，R 指的是 right。?

?三路劃分法的思想：

當 a[cur] < key，交換 cur 和 left 位置上的值，left++，cur++。
當 a[cur] >?key，交換 cur 和 right 位置上的值，right--。
當 a[cur] ==?key，cur++。

三路劃分法的本質：

小的甩到左邊，大的甩到右邊。、
與 key 值相等的值推到中間。

三路劃分法的結果：

[ begin , left-1 ] [ left , right ] [ right + 1 , end ]

三路劃分法代碼實現：

#include<stdio.h>// 快速排序--遞歸法---三路劃分法
void QuickSort1(int* a, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int key = a[left];int cur = left + 1;while (cur <= right){if (a[cur] > key){Swap(&a[cur], &a[right]);--right;}else if (a[cur] < key){Swap(&a[left], &a[cur]);++left;++cur;}else{++cur;}}// [begin,left-1][left,right][righ+1,end]QuickSort1(a, begin, left - 1);QuickSort1(a, right + 1, end);
}// 快速排序
int main()
{int a[] = { 6,1,6,7,9,6,4,5,6,8 };int sz = sizeof(a) / sizeof(a[0]);QuickSort(a, 0,sz-1);return 0;
}

六：快速排序——非遞歸實現

????????因為遞歸這個過程是在內存中的棧空間內實現的，但是在內存中棧所含有的空間很少，當遞歸層數太多時，往往存在棧溢出的情況，那么解決的方法，就是將遞歸版本改為非遞歸版本，這就需要借助以前學的棧（先進后出）這一工具來模擬實現非遞歸的快速排序，因為棧是在內存中的堆區實現的，而內存上的堆空間很大很大，完全不需要考慮空間溢出的問題。

實現非遞歸的思路：

入棧一定要保證先入右，再入左。
取兩次棧頂元素作為區間的 left 和 right。
對該區間進行單趟排序。排序完：[ left , keyi - 1 ] keyi [ keyi + 1 , right ]
重復2，3過程直到棧為空。

快速排序非遞歸代碼實現：

// 快速排序--非遞歸法
void QuickSortNonR(int* a, int begin, int end)
{Stack st;            // 定義一個棧STInit(&st);STPush(&st, end);    // 棧：先入右STPush(&st, begin);  // 再入左while (!STEmpty(&st)){int left = STTop(&st);    // 取棧頂作為 區間的左邊界STPop(&st);int right = STTop(&st);   // 取棧頂作為 區間的右邊界STPop(&st);int keyi = PartSort2(a, left, right);    // 單趟排序得出 keyi// [left,keyi-1]keyi[keyi+1,right]if (left < keyi - 1)                // 判斷該區間是否合法{STPush(&st, keyi - 1);STPush(&st, left);}if (keyi + 1 < right)               // 判斷該區間是否合法{STPush(&st, right);STPush(&st, keyi + 1);}}STDestroy(&st);
}

效果演示：

七：快速排序——優化

7.1：快速排序優化--->三數取中選key法

????????在快速排序問世以來，一些人發現，keyi 的位置，是影響快排效率的最大因素，將 keyi 放在合理的位置就可再次增大該排序的運行效率。因此就有一些大佬采用了三數取中的方法解決選 keyi 位置不合適的問題。

所謂三數取中：就是取頭，中，尾三個元素，比較大小，選擇那個排在中間的數據作為基準值 keyi 。再進行快速排序，這種優化方法就能使該排序效率比原來高。

?三數取中優化法代碼實現：

// 快速排序--優化1---三數取中選key
int GetMidIndex1(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[right] < a[left]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}

這樣一來，中間值的下標就被返回過來了，將其帶入到快排代碼中，讓它成為新的 keyi 。

// 快速排序--遞歸法
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int mid = GetMidIndex1(a, begin, end);Swap(&a[begin], &a[mid]);        // 再交換中間值位置與最左邊位置int keyi = PartSort3(a, begin, end);// [beign,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

7.2：快速排序優化--->隨機數生成選key法

有人說，三數取中法有些死板，所取的值只能是固定位置，于是又有人在基于三數取中優化法之上，進行了再次優化——隨機數生成選 key 法。

隨機數生成選 key 法：就是 mid 的值并不只能是 (left+right) / 2 得來的，而是由隨機數生成而來。即? mid = left + (rand() % (right - left))。

隨機數生成選 key 法代碼實現：

// 快速排序--優化2---隨機數選key
int GetMidIndex2(int* a, int left, int right)
{int mid = left + (rand() % (right - left));if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[right] < a[left]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}

7.3：快速排序優化--->小區間改造

? ? ? ? 因為快速排序是遞歸實現進行的，所以當遞歸到最后幾層時，數組中的值其實已經接近有序了，并且這時再次進行遞歸會極大占用棧(函數棧幀開辟的地方，函數的遞歸都是在棧中進行實現的)的空間。

由于我們的快排遞歸類似于二叉樹這樣的結構，即越到最后所遞歸的次數越多。所以我們對其進行優化，當其區間內個數小于等于 10 時，就使用插入排序算法對其進行排序

那么該如何將其帶入到快速排序的代碼中來呢？

小區間改造法代碼實現：

// 插入排序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int tmp = a[i];int end = i - 1;while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}// 快速排序--遞歸法
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}if (end - begin <= 10){InsertSort(a, end - begin + 1);    // [begin,end] 兩個閉區間，求個數要 +1return;}int mid = GetMidIndex2(a, begin, end);Swap(&a[begin], &a[mid]);int keyi = PartSort3(a, begin, end);// [beign,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}