快速排序

Partition 過(guò)程：將要排序的數(shù)據(jù)分成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小。快速排序整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

注：408原題中說(shuō)，對(duì)所有尚未確定最終位置的所有元素進(jìn)??遍處理稱為“?趟”排序，因此?次“劃分”≠?趟排序。因此，?次 Partition 可以確定?個(gè)元素的最終位置，??趟排序也許可以確定多個(gè)元素的最終位置。

需要注意的是，嚴(yán)蔚敏和殷人昆給出了兩種不同的快排方法。雖然兩種方法均正確，但排序中間步驟得到的序列不同，導(dǎo)致做題時(shí)對(duì)答案產(chǎn)生疑惑。本文對(duì)這兩種快排算法進(jìn)行總結(jié)與對(duì)比。

嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》P274

排序過(guò)程舉例：

以上述第一趟為例，快排的過(guò)程展示如下。先圈出最左邊的 49，把最左邊位置空出來(lái)，然后讓指針從最右邊的 49 開(kāi)始往左走。

代碼

// 一趟快排 int Partition(SqList &L, int low, int high) {pivotkey = L[low]; //用字表的第一個(gè)記錄記錄樞軸的位置while (low < high) {while (low < high && L[high] > pivotkey) --high; //將比樞軸記錄小的記錄移到低端L[low] = L[high];while (low < high && L[low] < pivotkey) ++low;L[high] = L[low]; //將比樞軸記錄大的記錄移到高端}L[low] = pivotkey; //樞軸記錄到位return low; //返回樞軸位置 }// 快速排序算法 void Qsort(Sqlist &L, int low, int high) {if (low < high) { //長(zhǎng)度大于1pivotloc = Partition(L, low, high); //將L一分為2QSort(L, low, pivotloc - 1); //對(duì)低子表遞歸排序，pivotloc是樞軸位置Qsort(L, pivotloc + 1, high); //對(duì)高子表遞歸排序} }

殷人昆《數(shù)據(jù)結(jié)構(gòu)》P406

排序過(guò)程舉例：

代碼

#include <iostream>#define LEN 9 using namespace std;void Print(int A[]) {for (int i = 0; i < LEN; i++) {cout << A[i] << " ";}cout << endl; }void Swap(int &a, int &b) {int tmp = a;a = b;b = tmp; }int Partition(int A[], int low, int high) {int pivotpos = low;int pivot = A[low];for (int i = low + 1; i < high + 1; ++i) {if (A[i] < pivot) {pivotpos++;if (pivotpos != i) {Swap(A[pivotpos], A[i]);}}}A[low] = A[pivotpos];A[pivotpos] = pivot;Print(A);return pivotpos; }void QuickSort(int A[], const int left, const int right) {if (left < right) {int privotpos = Partition(A, left, right);QuickSort(A, left, privotpos - 1);QuickSort(A, privotpos + 1, right);} }int main() {int A[] = {12, 2, 16, 30, 28, 10, 20, 6, 18}; //0~10QuickSort(A, 0, LEN - 1);return 0; }

測(cè)試用例

示例 1

初始序列：

20, 4, 34, 5, 16, 33, 18, 29, 2, 40, 7

每一次調(diào)用 Partition 的結(jié)果：

7 4 5 16 18 2 20 29 33 40 34 2 4 5 7 18 16 20 29 33 40 34 2 4 5 7 18 16 20 29 33 40 34 2 4 5 7 18 16 20 29 33 40 34 2 4 5 7 16 18 20 29 33 40 34 2 4 5 7 16 18 20 29 33 40 34 2 4 5 7 16 18 20 29 33 40 34 2 4 5 7 16 18 20 29 33 34 40

示例 2

初始序列：

12, 2, 16, 30, 28, 10, 20, 6, 18

每一次調(diào)用 Partition 的結(jié)果：

6 2 10 12 28 16 20 30 18 2 6 10 12 28 16 20 30 18 2 6 10 12 18 16 20 28 30 2 6 10 12 16 18 20 28 30

總結(jié)

以上是生活随笔為你收集整理的数据结构：严蔚敏、殷人昆快速排序规则不同的疑问的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。