???????快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法。

???????基本思想為∶任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。

void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return; int div = partion(array, left, right);QuickSort(array, left, div); QuickSort(array, div+1, right);
}

???????上述為快速排序遞歸實(shí)現(xiàn)的主框架，發(fā)現(xiàn)與二叉樹前序遍歷規(guī)則非常像，我們?cè)趯戇f歸框架時(shí)可想想二叉樹前序遍歷規(guī)則即可快速寫出來(lái)，后序只需分析如何按照基準(zhǔn)值來(lái)對(duì)區(qū)間中數(shù)據(jù)進(jìn)行劃分的方式即可。

將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見(jiàn)方式有:

????????1.hoare版本

????????2.挖坑法

????????3.前后指針版本

下面將介紹三種方法，在此之前我們現(xiàn)需寫一個(gè)三數(shù)取中代碼：

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

---

一、hoare版本

具體步驟

1. 先選取數(shù)組左邊的第一個(gè)數(shù)作為key，定義一個(gè)左下標(biāo)left指向最左邊的數(shù)，定義一個(gè)右下標(biāo)right指向最右邊的數(shù)。
2. 然后讓right先往左遍歷，找到第一個(gè)比key大的值，讓left后向右遍歷，找到第一個(gè)比key小的值。
3. 這時(shí)，左邊的值都比key小，右邊的值都比key大，交換left和right指向的值。
4. 這樣一趟排序就結(jié)束了，key就在了它應(yīng)該在的位置上。重復(fù)以上步驟，直到整個(gè)序列有序。

核心代碼

int PartSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

實(shí)驗(yàn)結(jié)果

---

二、挖坑法

具體步驟

???????首先設(shè)置兩個(gè)指針，一個(gè)指向數(shù)組的起始位置，一個(gè)指向數(shù)組的末尾位置。從末尾位置開始，向前遍歷，找到第一個(gè)小于基準(zhǔn)元素的元素，并將其填入起始位置的坑中。然后從起始位置開始，向后遍歷，找到第一個(gè)大于基準(zhǔn)元素的元素，并將其填入上一步所挖的坑中。重復(fù)上述步驟，直到起始位置和末尾位置相遇。此時(shí)，將基準(zhǔn)元素填入最后一個(gè)坑中，這樣就完成了一次分區(qū)操作。最后對(duì)分區(qū)后的左右兩個(gè)子數(shù)組，分別遞歸地進(jìn)行上述步驟。

核心代碼

int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);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;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

實(shí)驗(yàn)結(jié)果

---

三、前后指針版本

具體步驟

1. 選擇樞軸元素：在數(shù)組中選擇一個(gè)元素作為樞軸，一般選擇第一個(gè)元素或最后一個(gè)元素。

2. 初始化左右指針：左指針指向數(shù)組的第一個(gè)元素，右指針指向數(shù)組的最后一個(gè)元素。

3. 劃分過(guò)程：從前往后遍歷數(shù)組，當(dāng)找到一個(gè)比樞軸大的元素時(shí)，將左指針向右移動(dòng)一位；從后往前遍歷數(shù)組，當(dāng)找到一個(gè)比樞軸小的元素時(shí)，將右指針向左移動(dòng)一位。當(dāng)左指針大于等于右指針時(shí)，說(shuō)明已經(jīng)找到正確的位置，將樞軸與左指針?biāo)谖恢玫脑亟粨Q。

4. 遞歸處理：將樞軸左邊的部分作為新的子數(shù)組，遞歸調(diào)用快速排序函數(shù)；將樞軸右邊的部分作為新的子數(shù)組，遞歸調(diào)用快速排序函數(shù)。

核心代碼?

int PartSort3(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}

實(shí)驗(yàn)結(jié)果

---

四、非遞歸版本

???????快速排序的非遞歸版本是遞歸版本的一種優(yōu)化，主要是通過(guò)將遞歸過(guò)程轉(zhuǎn)化為循環(huán)來(lái)實(shí)現(xiàn)?；舅悸肥菍?shù)組分為兩部分，一部分比基準(zhǔn)值小，另一部分比基準(zhǔn)值大，然后對(duì)這兩部分分別進(jìn)行快速排序。這個(gè)過(guò)程可以通過(guò)循環(huán)來(lái)實(shí)現(xiàn)，而不是通過(guò)遞歸調(diào)用函數(shù)自身。

具體步驟

???????首先從數(shù)組中挑選一個(gè)元素作為基準(zhǔn)值，然后將所有小于基準(zhǔn)值的元素移動(dòng)到基準(zhǔn)值的左邊，將所有大于基準(zhǔn)值的元素移動(dòng)到基準(zhǔn)值的右邊。接下來(lái)，對(duì)基準(zhǔn)值左右兩邊的子數(shù)組分別進(jìn)行相同的操作，直到數(shù)組完全有序。

核心代碼

void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st) != 0)
{right = StackTop(&st);StackPop(&st);left = StackTop(&st);StackPop(&st);if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基準(zhǔn)值為分割點(diǎn)，形成左右兩部分：[left, div) 和 [div+1, right)StackPush(&st, div+1);StackPush(&st, right);StackPush(&st, left);StackPush(&st, div);
}StackDestroy(&s);
}

? ? ? ?感興趣的同學(xué)可以自行練習(xí)。

---

五、快速排序特性總結(jié)

? ? ? ? 1.快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序

????????2.時(shí)間復(fù)雜度:O(N*logN)

????????3.空間復(fù)雜度:O(logN)

????????4.穩(wěn)定性:不穩(wěn)定

---

結(jié)語(yǔ)：快速排序的相關(guān)分享到這里就結(jié)束了，希望對(duì)大家的學(xué)習(xí)會(huì)有幫助，如果大家有什么問(wèn)題或者不同的見(jiàn)解，歡迎大家的留言~~~