數據結構之快速排序算法（快排）【圖文詳解】

P. S.：以下代碼均在VS2019環境下測試，不代表所有編譯器均可通過。 P. S.：測試代碼均未展示頭文件stdio.h的聲明，使用時請自行添加。
??

在這里插入圖片描述

???????????????????????????????????????????博主主頁：LiUEEEEE
??????????????????? ??????????????????????????C語言專欄
????????????????????????????????????????????數據結構專欄
?????????????????????????????????????????力扣牛客經典題目專欄

1、快排的基本思想

??快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為

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

2、快排的四種實現方法

??快速排序有多種實現方法，其具體體現如下：

Hoare快速排序
挖坑法快速排序
前后指針法快速排序
非遞歸法快速排序

下文將對上述四種實現方法依次進行講解。

3、Hoare快速排序

??Hoare快速排序的示意圖如下所示：

在這里插入圖片描述
??其主要思想為：使用循環遍歷數組

將所給數組的第一個值的下標給予key變量和begin變量（下文中統一為keyi，方便理解其為下標地址而非數組成員值），將數組最后一個值的下標給予end變量。
開始執行是令end向數組左側遍歷，尋找數值比數組下標為keyi的值小的數，若未尋找到，則繼續向左側遍歷，若尋找到，則停止遍歷，轉而為begin向數組右側遍歷。
begin向數組右側遍歷，尋找數值比下標為keyi的值大的數，若尋找到，則交換數組中下標為end和begin的值。
若在begin與end遍歷過程中兩變量出現相等的情況，則退出循環，將數組中下標為keyi和end的值交換。
記錄下交換位置，令其為新的分割點，利用遞歸的思想，將數組根據新分割點分割的左右兩次子數組進行遞歸，直到出現新數組中L >= R。
遞歸結束。

??其遞歸思想的圖示如下，示例：成員為4,2,6,5,7,1,3,8,10,9的數組。
??當記錄交換位置為3，即會有新的子數組【0，2】【4，9】，使用新數組進行遞歸。

在這里插入圖片描述
??遞歸方法如上圖所示（除3外其余遞歸交換位置為虛構，需實際計算得到）。

Hoare快速排序代碼如下

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int PartSort1(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;int keyi = left;while (begin < end){while(begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[end], &a[begin]);}Swap(&a[end], &a[keyi]);keyi = begin;PartSort1(a, left, keyi - 1);PartSort1(a, keyi + 1, right);
}

4、挖坑法快速排序

??挖坑法快速排序示意圖如下所示：

在這里插入圖片描述
??其主要思想為：使用循環遍歷數組

將數組中keyi所在下標的值暫存起來，其位置看作坑位，先令end從右向左遍歷尋找比暫存值小的值，尋找到后，將end所指向的值放入坑中，而后end所指向的位置變成新坑。
再令begin從右向左尋找比暫存值大的值，尋找到后，將begin所指向的值放入坑中，而后begin所指向位置變為新坑。
在循環過程中若begin與end相遇，則將暫存之放入此時的坑中。
記錄下最后一個坑的位置視作分界點，從分界點處分出兩個新的子數組，進行下一輪遞歸，直至所分出的新數組L >= R。
遞歸結束。
??其遞歸示意圖與標題三中所展示一致，故不再做重復展示。

挖坑法快速排序代碼如下所示：

int PartSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[end] >= key){end--;}a[keyi] = a[end];keyi = end;while (begin < end && a[begin] <= key){begin++;}a[keyi] = a[begin];keyi = begin;}a[keyi] = key;PartSort2(a, left, end - 1);PartSort2(a, end + 1, right);
}

5、前后指針法快速排序

??前后指針法快速排序示意圖如下所示：

在這里插入圖片描述
??其主要思想為：

定義指針prev指向數組開始位置，cur指向數組開始第二個位置，并使用keyi記錄數組中用作比較的數。
令cur向數組右端遍歷，若出現小于keyi的數則停止遍歷，轉為prev進行遍歷。
令prev向數組右端遍歷，若出現大于keyi的數，則令其與cur交換位置，而后繼續進行cur的遍歷，直至cur達到數組末尾的下一位（即越界）。
當cur越界后將當前prev所代表的值與key所代表值進行交換，并將prev所處位置視為分界點，從分界點處分出兩個新的子數組進行遞歸，直至所遞歸的數組L >= R。
遞歸結束。
??其遞歸示意圖與標題三中所展示一致，故不再做重復展示。
前后指針法快速排序代碼如下所示：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int PartSort3(int* a, int left, int right)
{if (left >= right)return;int prev = left;int cur = prev + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && a[++prev] != a[key])Swap(&a[cur], &a[prev]);cur++;}Swap(&a[key], &a[prev]);PartSort3(a, left, prev - 1);PartSort3(a, prev + 1, right);
}

6、非遞歸法快速排序

??非遞歸的方法實現快速排序，其原理是使用棧來模擬代碼在系統中的棧中的遞歸過程，也可稱之為偽遞歸。
??有關棧的相關內容可在下方查看：

????????????????????????????????棧（使用順序表構建）

??其主要思想為：

使用棧來模擬系統中棧的功能，將數組的右左下標依次傳入棧中，每一次取其棧頂位置數據分別作為單詞快排的目標數組左下標和右下表（每一次取值后需刪除棧頂元素）。
在單次快排完成后判斷其在分段點所分兩個新的子數組左右下標是否合理（是否存在左下標大于或等于右下標的行為），若不存在則將右子數組右左下標依次推入棧中，而后將左子數組右左下標依次推入棧中，進行下一輪循環。
其循環判斷條件為棧中是否為空。
有關其入棧順序可不做過多研究，但要保證的前提是所取出數值需與操作數組的左右下標相對應，以避免不必要麻煩。
非遞歸法快速排序代碼如下所示：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void QuickSortNonR(int* a, int left, int right)
{ST s;STInit(&s);STPush(&s, right);STPush(&s, left);while (!STEmpty(&s)){int begin = STTop(&s);STPop(&s);int end = STTop(&s);STPop(&s);int prev = begin;int cur = prev + 1;int key = begin;while (cur <= end){if (a[cur] < a[key] && a[++prev] != a[key])Swap(&a[cur], &a[prev]);cur++;}Swap(&a[key], &a[prev]);if (prev + 1 < end){STPush(&s, end);STPush(&s, prev + 1);}if (begin < prev - 1){STPush(&s, prev - 1);STPush(&s, begin);}}STDestroy(&s);
}

7、快速排序的優化

?? 此優化可適用于任意方法的可快速排序。
??在日常生活中，我們所使用排序功能的目標對象可能不會想日常練習中那樣少，或許是一個非常龐大的數量，且其所提供的數據可能在原本基礎上就有部分有序化，例如所給的大量數據中第一位為最小值或最大值，而這樣的數據我們從一開始就進行快速排序的話，會讓end從末尾一直遍歷到數據首部或begin從數據首部一直遍歷到末尾，擁有時間復雜度上的浪費，所以我們提出了一個三數取中的方法來進行優化，且針對于大量數據，當所處理數據的子數據數量過少時，我們還是用快速排序的方法有點大材小用了，故針對于此我們也提出了少量數據另謀他法的方法應對。

7.1 三數取中

??針對于所給目標數組第一位即為最小值或最大值而導致的時間復雜度浪費，我們可以取其數組首位，中位，末位三個數進行比較，選取其中處于中間位置的數，令其與數據首位進行交換。

其代碼如下所示：

int GetMid(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;elsereturn right;}else{if (a[mid] < a[right])return mid;else if (a[right] < a[left])return left;elsereturn right;}
}

7.2 少量數據另謀他法

??對于根據分界點所得到的新子數組，若其數據量較小，我們還是用快速排序的化有些大材小用，故當數據量較小時，我們一般使用其他排序方法，如冒泡排序或插入排序等，進行快速的排序。

其代碼如下所示

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1])Swap(&a[j], &a[j + 1]);}}
}if (right - left < 10){BubbleSort(a, right - left + 1);}

??至此快速排序的優化結束，其完整代碼如下所示（前后指針法快速排序）：

void QuickSort(int* a, int left, int right)
{if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[left], &a[mid]);if (right - left < 10){BubbleSort(a, right - left + 1);}else{int prev = left;int cur = prev + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && a[++prev] != a[key])Swap(&a[cur], &a[prev]);cur++;}Swap(&a[key], &a[prev]);PartSort3(a, left, prev - 1);PartSort3(a, prev + 1, right);}
}