上集回顧

排序?qū)W習(xí)整理（1）-CSDN博客

2.3 交換排序

交換排序的基本思想是：根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果，交換這兩個(gè)記錄在序列中的位置。

特點(diǎn)：

• 通過比較和交換操作，將鍵值較大的記錄逐步移動(dòng)到序列的尾部，而鍵值較小的記錄逐步移動(dòng)到序列的前部。
• 重復(fù)此過程，直到整個(gè)序列變得有序。

2.3.1 冒泡排序?

冒泡排序（Bubble Sort）是一種簡單的交換排序算法，其核心思想是通過重復(fù)的比較和交換操作，將序列中的最大值或最小值逐步“冒泡”到序列的尾部或頭部。

基本思想

從序列的起始位置開始，依次比較相鄰的兩個(gè)元素：

????????????????如果它們的順序不正確（如升序時(shí)前一個(gè)大于后一個(gè)），則交換它們的位置。

一輪比較后，當(dāng)前未排序部分的最大值會(huì)被“冒泡”到末尾。

對剩下的未排序部分重復(fù)上述過程，直到整個(gè)序列有序。

算法步驟

1. 初始化一個(gè)外層循環(huán)，用來控制需要比較的輪數(shù)。
2. 在每輪循環(huán)中，從序列的開頭開始，逐一比較相鄰的兩個(gè)元素，完成交換。
3. 每輪排序結(jié)束后，未排序部分的長度減1。
4. 重復(fù)上述操作，直到不需要再比較。

?代碼實(shí)現(xiàn)

void BubbleSort(int* arr, int n) {for (int i = 0; i < n - 1; i++) {  // 控制排序輪數(shù)int swapped = 0;  // 標(biāo)記本輪是否發(fā)生交換for (int j = 0; j < n - 1 - i; j++) {  // 控制每輪比較次數(shù)if (arr[j] > arr[j + 1]) {  // 如果順序不正確int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;  // 標(biāo)記發(fā)生了交換}}if (!swapped) {  // 如果本輪沒有交換，說明已經(jīng)有序break;}}
}

特性總結(jié)

算法復(fù)雜度

1. 時(shí)間復(fù)雜度：
   • 最好情況（序列已排序）：O(n)
   • 最壞情況（序列逆序）：O(n^2)
   • 平均情況：O(n^2)
2. 空間復(fù)雜度：只需要常數(shù)級額外空間，空間復(fù)雜度為 O(1)。
3. 穩(wěn)定性：冒泡排序是穩(wěn)定的排序算法，因?yàn)樵诒容^相等元素時(shí)，它不會(huì)改變它們的相對位置。

---

優(yōu)缺點(diǎn)和適用場景就不介紹了，冒泡的效率太過于低下，基本只用于教學(xué)了

2.3.2 快速排序?

基本思想是：從待排序序列中隨機(jī)選取一個(gè)元素作為基準(zhǔn)值，依據(jù)該基準(zhǔn)值將序列劃分為兩個(gè)子序列，其中左子序列的所有元素都小于基準(zhǔn)值，右子序列的所有元素都大于基準(zhǔn)值。然后對左右子序列分別重復(fù)這一過程，直到所有元素都排列到正確的位置上為止。

?快速排序?qū)崿F(xiàn)的主框架

//快速排序
void QuickSort(int* a, int left, int right){if (left >= right) {return;}//_QuickSort?于按照基準(zhǔn)值將區(qū)間[left,right)中的元素進(jìn)?劃分int meet = _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet + 1, right);
}

主要有以下幾種實(shí)現(xiàn)方法：

2.3.2.1 hoare版本

Hoare版本的快速排序是由算法提出者Tony Hoare在1962年設(shè)計(jì)的一種經(jīng)典快速排序?qū)崿F(xiàn)。該版本利用分區(qū)的思想，將數(shù)組分成兩部分，使得一部分元素小于基準(zhǔn)值，另一部分元素大于基準(zhǔn)值。隨后對兩部分遞歸地應(yīng)用快速排序，直到數(shù)組有序。

基本思想

核心操作是“分區(qū)”，使用左右指針分別從兩端向中間掃描，找到需要交換的元素位置，最終將數(shù)組劃分為左右兩部分。

1. Hoare版本的快速排序通過分區(qū)的思想，將數(shù)組分成兩部分：

2. 左子數(shù)組中的元素均小于等于基準(zhǔn)值。
3. 右子數(shù)組中的元素均大于等于基準(zhǔn)值。 采用遞歸或迭代方式，對子數(shù)組繼續(xù)進(jìn)行快速排序，直到子數(shù)組長度為1或0，排序完成。

算法步驟

1. 選擇基準(zhǔn)值： 通常選擇當(dāng)前子數(shù)組的第一個(gè)元素作為基準(zhǔn)值。
2. 分區(qū)：
   • 設(shè)置左右兩個(gè)指針，分別指向當(dāng)前子數(shù)組的兩端。
   • 右指針向左移動(dòng)，找到第一個(gè)小于等于基準(zhǔn)值的元素。
   • 左指針向右移動(dòng)，找到第一個(gè)大于等于基準(zhǔn)值的元素。
   • 如果左右指針未交錯(cuò)，交換兩指針指向的元素，繼續(xù)移動(dòng)指針。
   • 當(dāng)左右指針交錯(cuò)時(shí)，分區(qū)完成，并返回分界點(diǎn)。
3. 遞歸排序：
   • 將數(shù)組按照分界點(diǎn)劃分為左右兩部分。
   • 分別對左右部分遞歸執(zhí)行上述過程，直到子數(shù)組長度為1或0。

?問題1：為什么跳出循環(huán)后right位置的值?定不大于key？

當(dāng) left > right 時(shí)，右指針（right）已經(jīng)移動(dòng)到了左指針（left）的左側(cè)。由于在分區(qū)過程中，左指針從左到右掃描的所有數(shù)據(jù)均不大于基準(zhǔn)值（key），因此，跳出循環(huán)時(shí)，右指針（right）所指向的數(shù)據(jù)一定不大于基準(zhǔn)值（key）。

????????

問題2：為什么left 和 right指定的數(shù)據(jù)和key值相等時(shí)也要交換？

相等的值參與交換確實(shí)有一些額外消耗，但在實(shí)際中，數(shù)組可能存在大量重復(fù)元素，如果相等的值不參與交換，可能導(dǎo)致分區(qū)無法有效進(jìn)行，從而影響排序的正確性和效率。

代碼實(shí)現(xiàn)

// 交換函數(shù)
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
// 快速排序
void QuickSort(int* a, int left, int right) {if (left >= right) { // 遞歸邊界條件：區(qū)間只有一個(gè)元素或無元素return;}int begin = left, end = right; // 記錄當(dāng)前區(qū)間int keyi = left; // 基準(zhǔn)值初始為第一個(gè)元素的下標(biāo)while (left < right) {// 從右向左尋找比基準(zhǔn)值小的元素while (a[right] >= a[keyi] && left < right) {right--;}// 從左向右尋找比基準(zhǔn)值大的元素while (a[left] <= a[keyi] && left < right) {left++;}// 交換左右指針指向的值Swap(&a[left], &a[right]);}// 基準(zhǔn)值歸位Swap(&a[left], &a[keyi]);keyi = left; // 更新基準(zhǔn)值位置// 對左右兩部分遞歸排序QuickSort(a, begin, keyi - 1); // 左部分QuickSort(a, keyi + 1, end);   // 右部分
}

特性總結(jié)

算法復(fù)雜度

時(shí)間復(fù)雜度：

????????????????最好情況：O(n log?n)，每次分區(qū)都能平均劃分為兩半。

????????????????最壞情況：O(n^2)，當(dāng)基準(zhǔn)值總是選擇到最小或最大值時(shí)，分區(qū)極不均衡。

????????????????平均情況：O(n log?n)，這是快速排序的典型表現(xiàn)。

空間復(fù)雜度：

????????????????O(log?n)：遞歸調(diào)用棧的深度。

---

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 時(shí)間復(fù)雜度低：平均性能優(yōu)于大多數(shù)排序算法，適合大規(guī)模數(shù)據(jù)。
2. 原地排序：不需要額外的內(nèi)存（僅遞歸?？臻g）。
3. 實(shí)現(xiàn)簡單：通過分區(qū)邏輯實(shí)現(xiàn)高效的遞歸。

缺點(diǎn)：

1. 不穩(wěn)定：相同元素的相對順序可能改變。
2. 最壞情況效率低：對于完全有序或接近有序的數(shù)據(jù)，性能可能退化為O(n^2)。
3. 遞歸調(diào)用棧問題：當(dāng)數(shù)據(jù)規(guī)模過大時(shí)，遞歸調(diào)用深度可能導(dǎo)致棧溢出。

---

適用場景

1. 大規(guī)模數(shù)據(jù)排序：快速排序在大數(shù)據(jù)場景下表現(xiàn)良好。
2. 對穩(wěn)定性無要求的場景：例如數(shù)字或字符排序。
3. 通用排序需求：適合隨機(jī)分布的無序數(shù)據(jù)集。

很明顯的缺點(diǎn)不少，接下來介紹針對不同情況優(yōu)化的另外三種快排

?2.3.2.2 挖坑法

挖坑法（也稱為坑填法或坑填交換法）是一種在排序算法中常用的技巧，特別是在快速排序和堆排序等算法的實(shí)現(xiàn)中。常用于處理兩個(gè)元素交換問題，并且通常配合雙指針或者分區(qū)操作來完成排序。

挖坑法在大量重復(fù)元素的情況下能減少交換次數(shù)，因此在這些場景下的優(yōu)化效果明顯。

基本思想

在元素交換過程中使用一個(gè)臨時(shí)“坑”來存儲一個(gè)元素的值，避免出現(xiàn)直接交換時(shí)元素覆蓋的情況。這使得元素能夠順利地放到正確的位置，并且交換過程更加高效。

在快速排序的分區(qū)操作中，使用兩個(gè)指針分別從兩端掃描，遇到需要交換的元素時(shí)，利用“坑”存儲其中一個(gè)元素，等另一個(gè)元素找到合適位置后再進(jìn)行交換。最終基準(zhǔn)值會(huì)被放置到“坑”中，實(shí)現(xiàn)正確的分區(qū)。

?算法步驟

• 選擇基準(zhǔn)值：選擇一個(gè)元素作為基準(zhǔn)值（通常是第一個(gè)元素，或隨機(jī)選擇一個(gè)）。
• 左右指針掃描：

????????????????右指針從右側(cè)開始，向左掃描，找到一個(gè)小于等于基準(zhǔn)值的元素。

????????????????左指針從左側(cè)開始，向右掃描，找到一個(gè)大于等于基準(zhǔn)值的元素。

• 交換元素：

????????????????如果左指針和右指針沒有交錯(cuò)，就交換這兩個(gè)元素。

????????????????交換時(shí)，使用一個(gè)臨時(shí)“坑”來存放其中一個(gè)元素的值，避免覆蓋問題。

• 繼續(xù)掃描：重復(fù)步驟2和步驟3，直到左右指針交錯(cuò)。
• 放置基準(zhǔn)值：當(dāng)左右指針交錯(cuò)時(shí)，將基準(zhǔn)值放入當(dāng)前“坑”位置，即完成分區(qū)。
• 遞歸排序：對左右兩部分繼續(xù)遞歸執(zhí)行快速排序。

代碼實(shí)現(xiàn)

void QuickSort(int* a, int left, int right) {if (left >= right) {return; // 當(dāng)區(qū)間為空或只有一個(gè)元素時(shí)，遞歸結(jié)束}int begin = left;int end = right;int keyi = a[left]; // 基準(zhǔn)值while (left < right) {// 從右向左尋找比基準(zhǔn)值小的數(shù)while (a[right] >= keyi && left < right) {right--;}if (left < right) {a[left] = a[right]; // 填坑}// 從左向右尋找比基準(zhǔn)值大的數(shù)while (a[left] <= keyi && left < right) {left++;}if (left < right) {a[right] = a[left]; // 填坑}}// 最后將基準(zhǔn)值填入當(dāng)前坑位a[left] = keyi;// 對左右區(qū)間遞歸排序QuickSort(a, begin, left - 1); // 左區(qū)間QuickSort(a, left + 1, end);   // 右區(qū)間
}

復(fù)雜度優(yōu)缺點(diǎn)什么的和hoare版差不多，就介紹下與hoare法相對的優(yōu)化情況吧

• 減少了交換次數(shù)：Hoare法在某些情況下需要交換多個(gè)位置，尤其是當(dāng)掃描到不滿足條件的元素時(shí)。挖坑法則通過填坑和直接交換，使得不需要頻繁交換，進(jìn)一步提升了效率。

• 保持?jǐn)?shù)據(jù)的穩(wěn)定性：挖坑法對于數(shù)據(jù)的處理方式相對較為穩(wěn)定，避免了一些冗余的交換，且能夠使得算法執(zhí)行過程中更有序。

• 提高了數(shù)據(jù)的分區(qū)效果：挖坑法有助于實(shí)現(xiàn)更平衡的分區(qū)，尤其是在遇到重復(fù)元素或者大范圍的相同值時(shí)，能夠更均勻地進(jìn)行分割。由于它通過“填坑”的方式保持了分區(qū)的連續(xù)性，因此在數(shù)據(jù)比較“均勻”的情況下能夠帶來較好的分割效果。

?2.3.2.3 前后指針法

前后指針法（Two-pointer technique）是一種常用的技術(shù)，通常用于排序算法中的分區(qū)操作，特別是在快速排序的分區(qū)階段。它通過設(shè)置兩個(gè)指針從數(shù)組的兩端向中間掃描，逐步找到需要交換的位置，從而實(shí)現(xiàn)分區(qū)操作。

前后指針法對于提高交換效率和減少不必要的交換有很大幫助，尤其是在數(shù)據(jù)量大且分布不均勻時(shí)

基本思想

• 使用兩個(gè)指針，一個(gè)從數(shù)組的左端開始（前指針），另一個(gè)從數(shù)組的右端開始（后指針）。
• 前指針向右掃描，直到找到一個(gè)大于等于基準(zhǔn)值的元素；后指針向左掃描，直到找到一個(gè)小于等于基準(zhǔn)值的元素。
• 當(dāng)前指針小于后指針時(shí)，交換這兩個(gè)元素。交換后，繼續(xù)移動(dòng)兩個(gè)指針，直到指針交錯(cuò)或相遇。
• 當(dāng)指針交錯(cuò)時(shí)，結(jié)束掃描，將基準(zhǔn)值放到指針交錯(cuò)的位置，完成分區(qū)。

算法步驟

1. 選擇基準(zhǔn)值：選擇一個(gè)基準(zhǔn)值，通常選擇數(shù)組的第一個(gè)元素或者最后一個(gè)元素。
2. 初始化指針：設(shè)置兩個(gè)指針，前指針（left）指向數(shù)組的起始位置，后指針（right）指向數(shù)組的結(jié)束位置。
3. 掃描交換：
   • 前指針：從左向右掃描，找到第一個(gè)大于等于基準(zhǔn)值的元素。
   • 后指針：從右向左掃描，找到第一個(gè)小于等于基準(zhǔn)值的元素。
   • 如果前指針小于后指針，則交換這兩個(gè)元素，繼續(xù)掃描。
4. 基準(zhǔn)值放置：當(dāng)指針交錯(cuò)或相遇時(shí)，將基準(zhǔn)值放入指針交錯(cuò)的位置，實(shí)現(xiàn)分區(qū)。
5. 遞歸排序：對左側(cè)和右側(cè)子數(shù)組進(jìn)行遞歸排序。

代碼實(shí)現(xiàn)

Swap函數(shù)和上面的一樣，就不再水一次了

void QuickSort(int* a, int left, int right) {// 如果區(qū)間無效或只剩一個(gè)元素，直接返回if (left >= right) {return;}// 設(shè)置初始基準(zhǔn)值的位置（選取左邊的元素作為基準(zhǔn)值）int prev = left; ?// prev 用于標(biāo)記小于基準(zhǔn)值的區(qū)域的末尾位置int cur = prev + 1; ?// cur 用于遍歷數(shù)組int pivotIndex = left; ?// 基準(zhǔn)值的位置（初始化為左邊界）// 遍歷整個(gè)區(qū)間，進(jìn)行分區(qū)while (cur <= right) {// 如果當(dāng)前元素小于基準(zhǔn)值并且 prev 位置還沒有與 cur 交換if (a[cur] < a[pivotIndex] && ++prev != cur) {// 如果符合條件，則交換 a[prev] 和 a[cur]Swap(&a[prev], &a[cur]);}++cur; ?// 繼續(xù)向右移動(dòng) cur 指針}// 最后將基準(zhǔn)值與 prev 位置的元素交換，將基準(zhǔn)值放到正確的位置Swap(&a[prev], &a[pivotIndex]);pivotIndex = prev; ?// 更新基準(zhǔn)值位置// 遞歸處理左右兩個(gè)子區(qū)間QuickSort(a, left, pivotIndex - 1); ?// 處理左區(qū)間QuickSort(a, pivotIndex + 1, right); ?// 處理右區(qū)間
}

算法復(fù)雜度和優(yōu)缺點(diǎn)一樣繼續(xù)與hoare同，優(yōu)化在于

• 減少了交換次數(shù)：在Hoare法中，當(dāng)左右指針掃描時(shí)，可能會(huì)在每次比較時(shí)都進(jìn)行交換。而前后指針法則是只在需要時(shí)才交換，并且掃描過程是從兩端開始的，能夠更高效地找到合適的交換元素。

• 提高了分區(qū)效率：前后指針法可以確保左右指針每次都能找到需要交換的元素，因此比傳統(tǒng)的Hoare法可能更快地將數(shù)據(jù)分割為兩部分。這種方法避免了多個(gè)不必要的交換，提高了分區(qū)的速度。

• 優(yōu)化情況：當(dāng)數(shù)據(jù)的順序比較混亂，或者大部分元素都較接近基準(zhǔn)值時(shí)，前后指針法能夠更有效地進(jìn)行數(shù)據(jù)分割，減少了不必要的比較和交換操作。

2.3.2.4?非遞歸版本

餃子醋來咯，嘗試盡量講清楚

首先，這個(gè)版本需要棧來實(shí)現(xiàn)，學(xué)了棧再來，先上官方一點(diǎn)的介紹

傳統(tǒng)的快速排序算法通常使用遞歸來實(shí)現(xiàn)分區(qū)和排序操作，但在某些情況下（例如，當(dāng)遞歸深度過大時(shí)，可能導(dǎo)致棧溢出），可以使用非遞歸版的快速排序來避免遞歸帶來的開銷。非遞歸版快速排序使用顯式的棧來模擬遞歸的調(diào)用，借助棧保存子數(shù)組的邊界，逐步進(jìn)行分區(qū)和排序。

非遞歸版則主要解決了遞歸帶來的棧溢出問題，適合處理大規(guī)模數(shù)據(jù)或?？臻g受限的情況，但對于排序速度并沒有顯著提高。?

基本思想

非遞歸版快速排序的基本思想是：????????

• 使用棧代替遞歸的調(diào)用棧，通過顯式地維護(hù)子數(shù)組的起始和結(jié)束位置。
• 每次分區(qū)操作后，將新的左右子數(shù)組的邊界壓入棧中，繼續(xù)分區(qū)，直到棧為空。
• 由于棧模擬了遞歸過程，因此在內(nèi)存方面比傳統(tǒng)遞歸方法更加高效。

算法步驟

1. 初始化棧：初始化一個(gè)棧，用來存儲子數(shù)組的左右邊界。
2. 壓入初始邊界：將整個(gè)數(shù)組的左右邊界壓入棧中（即初始的低位和高位）。
3. 分區(qū)操作：
   • 從棧中彈出一個(gè)子數(shù)組的邊界（即子數(shù)組的左端點(diǎn)和右端點(diǎn)）。
   • 對該子數(shù)組進(jìn)行分區(qū)操作，將其分為兩個(gè)部分，基準(zhǔn)值將放在正確位置。
4. 壓入子數(shù)組的邊界：根據(jù)分區(qū)結(jié)果，將兩個(gè)子數(shù)組的邊界壓入棧中，繼續(xù)分區(qū)。
5. 循環(huán)直到棧為空：重復(fù)上述步驟，直到棧為空，即所有子數(shù)組都被處理完。

其實(shí)就記住這個(gè)操作就好了，取棧頂區(qū)間，單趟排序，右左子區(qū)間入棧，不斷重復(fù)及完成了整個(gè)函數(shù)。

?

代碼實(shí)現(xiàn)

void QuickSortNonR(int* a, int left, int right) {ST st;STInit(&st);  // 初始化棧STPush(&st, right);  // 將右邊界入棧STPush(&st, left);  // 將左邊界入棧// 循環(huán)棧中的區(qū)間進(jìn)行排序while (!STEmpty(&st)) {int begin = STTop(&st);  // 獲取當(dāng)前區(qū)間的左邊界STPop(&st);  // 彈出左邊界int end = STTop(&st);  // 獲取當(dāng)前區(qū)間的右邊界STPop(&st);  // 彈出右邊界int keyi = begin;  // 選擇基準(zhǔn)元素的初始位置int cur = begin + 1;  // 當(dāng)前元素指針int prev = begin;  // 上一個(gè)小于基準(zhǔn)元素的位置// 對區(qū)間內(nèi)的元素進(jìn)行排序while (cur <= end) {if (a[cur] < a[keyi] && ++prev != cur)  // 如果當(dāng)前元素小于基準(zhǔn)元素，則交換Swap(&a[prev], &a[cur]);++cur;}// 將基準(zhǔn)元素放到正確的位置Swap(&a[keyi], &a[prev]);keyi = prev;  // 更新基準(zhǔn)元素位置// 如果基準(zhǔn)元素右邊還有元素，繼續(xù)排序右邊區(qū)間if (keyi + 1 < end) {STPush(&st, end);STPush(&st, keyi + 1);}// 如果基準(zhǔn)元素左邊還有元素，繼續(xù)排序左邊區(qū)間if (keyi - 1 > begin) {STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);  // 銷毀棧
}

棧實(shí)現(xiàn)的代碼拿的是自己上次的棧的實(shí)現(xiàn)（基礎(chǔ)）-CSDN博客

特性總結(jié)

算法復(fù)雜度

時(shí)間復(fù)雜度不變，空間復(fù)雜度正常也是?O(log?n)，但在最壞情況（有序或接近有序）會(huì)到O(n)

---

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 避免棧溢出：非遞歸版的快速排序通過顯式的棧來模擬遞歸，避免了因遞歸深度過大而導(dǎo)致棧溢出的風(fēng)險(xiǎn)。
2. 節(jié)省棧空間：在遞歸方法中，棧的空間隨著遞歸深度的增加而增加，而非遞歸版的快速排序通過顯式棧管理，節(jié)省了遞歸?？臻g。

缺點(diǎn)：

1. 代碼復(fù)雜度增加：非遞歸版的快速排序?qū)崿F(xiàn)需要額外的棧結(jié)構(gòu)來模擬遞歸，增加了代碼的復(fù)雜性。
2. 空間開銷：盡管非遞歸版避免了遞歸棧的開銷，但仍然需要額外的?？臻g來存儲子數(shù)組的邊界，尤其對于大數(shù)組時(shí)，空間開銷可能較大。

---

適用場景

1. 遞歸深度較大時(shí)：當(dāng)數(shù)據(jù)集非常大或遞歸深度較深時(shí)，非遞歸版快速排序通過避免棧溢出，使得排序過程更穩(wěn)定。
2. 內(nèi)存限制：如果系統(tǒng)的?？臻g有限，遞歸深度可能會(huì)導(dǎo)致棧溢出，此時(shí)非遞歸版更為適用。
3. 需要改進(jìn)性能的應(yīng)用場景：對于一些對性能要求較高的應(yīng)用，避免遞歸棧開銷可能會(huì)帶來一定的性能提升。

2.3.2.5?優(yōu)化方法

2.3.2.5.1 三數(shù)取中

這個(gè)方法針對前面4種都不利的有序數(shù)組，從這個(gè)角度出發(fā)，我們有了三數(shù)取中的優(yōu)化方式：

即選出mid=(left+right)/2

a[left]、a[right]、a[mid]這三個(gè)數(shù)中，值為中位數(shù)的那個(gè)數(shù)，然后將它于a[keyi]交換。

下面代碼基于前后指針法

// 三數(shù)取中法
int GetMidi(int* a, int begin, int end) {// 計(jì)算中間元素的索引int mid = begin + ((end - begin) >> 1);// 判斷mid元素是否在begin和end之間（即a[mid] 是位于 [a[begin], a[end]] 之間）if ((a[mid] >= a[begin] && a[mid] <= a[end]) || (a[mid] >= a[end] && a[mid] <= a[begin])) {return mid;  // 如果mid符合條件，返回mid的索引}// 如果a[begin]比a[mid]大，且a[begin]比a[end]小，或者a[begin]比a[mid]小，且a[begin]比a[end]大if ((a[begin] <= a[mid] && a[begin] >= a[end]) ||(a[begin] >= a[mid] && a[begin] <= a[end])) {return begin;  // 返回begin的索引}// 默認(rèn)返回end的索引return end;
}// 快速排序主函數(shù)
int QuickSort(int* a, int begin, int end) {// 三數(shù)取中法優(yōu)化：選擇begin, mid, end三個(gè)元素的中位數(shù)作為基準(zhǔn)元素int ki = GetMidi(a, begin, end); // 獲取中位數(shù)元素的索引Swap(&a[begin], &a[ki]);  // 將中位數(shù)元素與begin位置的元素交換int keyi = begin;  // keyi是基準(zhǔn)元素的初始位置int prev = begin;  // prev是掃描過程中已排序元素的最右邊的位置int next = begin + 1;  // next是當(dāng)前掃描到的元素位置// 前后指針法進(jìn)行分區(qū)操作while (next <= end) {// 如果當(dāng)前元素小于基準(zhǔn)元素，交換到prev位置，并更新prev的位置if (a[next] < a[keyi] && ++prev != next) {Swap(&a[prev], &a[next]);}next++;  // 移動(dòng)next指針，掃描下一個(gè)元素}// 將基準(zhǔn)元素放到正確的位置（即prev位置），并返回基準(zhǔn)元素的位置Swap(&a[keyi], &a[prev]);return prev;  // 返回基準(zhǔn)元素的最終位置
}

注釋這么詳細(xì)就不用額外介紹了吧（

來下一個(gè)優(yōu)化

2.3.2.5.2 小區(qū)間優(yōu)化

當(dāng)區(qū)間很小時(shí)，直接采用插入排序，就不用繼續(xù)遞歸了。

void QuickSort(int* a, int left, int right)
{// 如果區(qū)間內(nèi)的元素只有一個(gè)或沒有，直接返回，因?yàn)橐呀?jīng)是最小子問題（即已經(jīng)排好序）if (left >= right)return;// 對于小區(qū)間（小于10個(gè)元素），使用插入排序，可以減少遞歸深度，提高效率if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);  // 對[a+left, right]區(qū)間的元素進(jìn)行插入排序}else{int begin = left, end = right;int midi = GetMidi(a, left, right);  // 獲取三數(shù)取中的基準(zhǔn)索引Swap(&a[left], &a[midi]);  // 將基準(zhǔn)元素交換到left位置// 定義keyi為基準(zhǔn)元素的索引，進(jìn)行分區(qū)操作int keyi = left;// 進(jìn)行前后指針法分區(qū)while (left < right){// 從右邊開始，找一個(gè)小于基準(zhǔn)的元素while (left < right && a[right] >= a[keyi]){--right;  // right指針向左移動(dòng)}// 從左邊開始，找一個(gè)大于基準(zhǔn)的元素while (left < right && a[left] <= a[keyi]){++left;  // left指針向右移動(dòng)}// 找到符合條件的元素后交換Swap(&a[left], &a[right]);}// 將基準(zhǔn)元素放到正確的位置（即left位置），完成分區(qū)Swap(&a[left], &a[keyi]);keyi = left;// 遞歸調(diào)用對左右子數(shù)組進(jìn)行排序QuickSort1(a, begin, keyi - 1);  // 對左子數(shù)組進(jìn)行排序QuickSort1(a, keyi + 1, end);    // 對右子數(shù)組進(jìn)行排序}
}

下一篇就講歸并排序和非比較排序吧，估計(jì)不長了