前言

1，數(shù)據(jù)結(jié)構(gòu)排序篇章是一個(gè)大的工程，這里是一個(gè)總結(jié)篇章，配備動(dòng)圖和過程詳解，從難到易逐步解析。

2，這里我們?cè)敿?xì)分析幾個(gè)具備教學(xué)意義和實(shí)際使用意義的排序：

冒泡排序，選擇排序，插入排序，希爾排序，快排（遞歸，霍爾版本），快排（遞歸，前后指針版本），快排（非遞歸版本），堆排序（解決top_k問題），歸并排序（遞歸），歸并排序（非遞歸），計(jì)數(shù)排序

3，這里我想說一下，學(xué)習(xí)排序之前需要了解一些相關(guān)的知識(shí)，

1. 復(fù)雜度：目的是了解算法的時(shí)間復(fù)雜度，復(fù)雜度精講（時(shí)間+空間）-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138073981
2. 棧和隊(duì)列：目的是在排序非遞歸實(shí)現(xiàn)里面，我們需要用到棧，比如速排的非遞歸實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列(速通版本)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138715165
3. 二叉樹：目的是在排序計(jì)算里面，遞歸的解決方式是比較常用的方式，二叉樹正好是用遞歸來完成的，可以輔助我們深入的了解一下排序的遞歸數(shù)據(jù)結(jié)構(gòu)-二叉樹系統(tǒng)性學(xué)習(xí)（四萬字精講拿捏）-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138799868

4，當(dāng)然最后一點(diǎn)就是這些知識(shí)也可以不直接涉及到，如果你的時(shí)間比較緊張的話，只是理解起來相對(duì)而言需要一點(diǎn)難度，這些知識(shí)不是必須的。需要知道的是，這些知識(shí)可以幫助你深入理解排序的邏輯。

5，對(duì)于排序的學(xué)習(xí)很重要的一點(diǎn)就是，每次實(shí)現(xiàn)的時(shí)候我們往往需要先實(shí)現(xiàn)單趟排序的實(shí)現(xiàn)，之后再實(shí)現(xiàn)多趟的完結(jié)，這個(gè)是很重要的思路

6，這里的代碼觀看，尤其是對(duì)于排序代碼的實(shí)現(xiàn)

• 先看內(nèi)循環(huán)，因?yàn)閮?nèi)循環(huán)是單趟實(shí)現(xiàn)
• 再看外循環(huán)，因?yàn)橥庋h(huán)是全部實(shí)現(xiàn)邏輯。
• 這里一定不能搞錯(cuò)順序，不然數(shù)據(jù)結(jié)構(gòu)排序篇章很容易就無法看懂。
• 并且單趟實(shí)現(xiàn)往往重于多趟實(shí)現(xiàn)，因?yàn)槎嗵藢?shí)現(xiàn)往往是單趟循環(huán)的循環(huán)和重復(fù)

冒泡排序

前言

冒泡排序具備很強(qiáng)的教學(xué)意義，但是沒有什么實(shí)踐意義，這里作為第一個(gè)講解的排序，目的是從簡(jiǎn)單開始講解，方便理解

冒泡排序gif

冒泡排序單趟實(shí)現(xiàn)

冒泡排序一次只解決一個(gè)數(shù)字，交換一個(gè)數(shù)字之后，開始交換第二個(gè)數(shù)字

那么多趟實(shí)現(xiàn)就直接for循環(huán)多趟實(shí)現(xiàn)就可以了

冒泡排序多趟實(shí)現(xiàn)邏輯

舉例2（無法理解可以先不看舉例2，這里是參照組）：

假設(shè)初始數(shù)組： [4, 2, 9, 1, 5]
第一輪后： [2, 4, 9, 1, 5] (9移到末尾)
第二輪后： [2, 4, 1, 5, 9] (9和5移到末尾)
第三輪后： [2, 1, 4, 5, 9] (9、5和4移到末尾)
第四輪后： [1, 2, 4, 5, 9] (9、5、4和2移到末尾)
第五輪后： [1, 2, 4, 5, 9] (數(shù)組已經(jīng)排序完成)

冒泡排序注意事項(xiàng)

單趟循環(huán)需要注意事項(xiàng)

這里如果傳參如果傳遞是是n，那么單趟實(shí)現(xiàn)的時(shí)候，我們不能循環(huán)n次數(shù)，只能循環(huán)n-1次數(shù)，因?yàn)?/p>

多趟循環(huán)需要注意事項(xiàng)

冒泡排序的交換邏輯

冒泡排序代碼實(shí)現(xiàn)

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//冒泡排序
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]);}}}
}

解釋：

1. 交換函數(shù)（Swap）：

   • 函數(shù)原型：void Swap(int* p1, int* p2)
   • 參數(shù)：p1?和?p2?是指向兩個(gè)整數(shù)的指針。
   • 功能：交換兩個(gè)指針?biāo)赶虻恼麛?shù)的值。
   • 實(shí)現(xiàn)：首先，使用一個(gè)臨時(shí)變量?tmp?存儲(chǔ)?p1?指向的值。然后將?p2?指向的值賦給?p1?指向的位置，最后將臨時(shí)變量?tmp（原來?p1?的值）賦給?p2?指向的位置。

2. 冒泡排序（BubbleSort）：

   • 函數(shù)原型：void BubbleSort(int* a, int n)
   • 參數(shù)：a?是指向整數(shù)數(shù)組的指針，n?是數(shù)組中元素的數(shù)量。
   • 功能：對(duì)數(shù)組?a?進(jìn)行原地排序，使數(shù)組中的元素按照非遞減順序排列。
   • 實(shí)現(xiàn)：冒泡排序通過重復(fù)遍歷要排序的數(shù)組，比較相鄰元素，如果它們的順序錯(cuò)誤就把它們交換過來。遍歷數(shù)組的工作是在外層循環(huán)中完成的，內(nèi)層循環(huán)負(fù)責(zé)實(shí)際的比較和交換。
3. 交換函數(shù)就是一個(gè)交換函數(shù)，因?yàn)楹竺嫖疫€需要調(diào)用，所以這里我單獨(dú)拿出來。

冒泡排序時(shí)間復(fù)雜度計(jì)算

冒泡排序的時(shí)間復(fù)雜度計(jì)算基于算法執(zhí)行的比較和交換操作的次數(shù)。下面是冒泡排序的時(shí)間復(fù)雜度分析：

1. 最佳情況：當(dāng)數(shù)組已經(jīng)完全有序時(shí)，冒泡排序只需要進(jìn)行一次遍歷即可確定數(shù)組已經(jīng)有序，不需要進(jìn)行任何交換。在這種情況下，時(shí)間復(fù)雜度是 O(n)，其中 n 是數(shù)組的長度。

2. 平均情況和最壞情況：在平均情況和最壞情況下，冒泡排序需要進(jìn)行 n-1 次遍歷，每次遍歷中進(jìn)行的比較次數(shù)依次減少。具體來說：

   • 第一次遍歷最多進(jìn)行 n-1 次比較。
   • 第二次遍歷最多進(jìn)行 n-2 次比較。
   • ...
   • 最后一次遍歷進(jìn)行 1 次比較。

   總的比較次數(shù)可以表示為：(n-1) + (n-2) + ... + 1。這是一個(gè)等差數(shù)列求和問題，其和為 n(n-1)/2。因此，平均情況和最壞情況下的時(shí)間復(fù)雜度是 O(n^2)。

3. 空間復(fù)雜度：冒泡排序是原地排序算法，它不需要額外的存儲(chǔ)空間來創(chuàng)建另一個(gè)數(shù)組，只需要一個(gè)臨時(shí)變量用于交換元素。因此，冒泡排序的空間復(fù)雜度是 O(1)。

4. 穩(wěn)定性：冒泡排序是穩(wěn)定的排序算法，因?yàn)樗粫?huì)改變相同元素之間的相對(duì)順序。

總結(jié)來說，冒泡排序的時(shí)間復(fù)雜度是：

• 最佳情況：O(n)
• 平均情況：O(n^2)
• 最壞情況：O(n^2)

由于冒泡排序在大多數(shù)情況下效率不高，特別是對(duì)于大數(shù)據(jù)集，它通常不作為首選排序算法。然而，它的簡(jiǎn)單性和穩(wěn)定性使其在某些特定情況下（如小數(shù)據(jù)集或基本有序的數(shù)據(jù)）仍然有用。

直接選擇排序

前言

直接選擇排序也是一個(gè)比較簡(jiǎn)單的排序，所以這里放在第二個(gè)進(jìn)行講解，這里和冒泡排序是有一點(diǎn)相似。直接選擇排序和冒泡排序一樣，也是具備一定的教學(xué)意義，但是沒有什么實(shí)際操作的意義，因?yàn)橹苯舆x擇排序的時(shí)間復(fù)雜度比較高，書寫起來和插入排序又差不多，所以沒有必要寫直接選擇排序。

直接選擇排序gif

直接選擇排序單趟實(shí)現(xiàn)

1，初始化min（最小值）=0（也就是最左邊的下標(biāo)）的元素為最小值

2，遍歷數(shù)組，如果此時(shí)出現(xiàn)更小的元素，這個(gè)元素的下標(biāo)是i，那么我們?cè)O(shè)定min=i

3，之后交換最左邊的元素和數(shù)值最小元素，因?yàn)檫@個(gè)時(shí)候我們已經(jīng)找到下標(biāo)了

4，最后排序好的最小值放在了最左邊，那么此時(shí)最左邊所在位置不需要進(jìn)行排序了，分離出來就可以

5，這里因?yàn)檫x擇排序效率太低了 ，我們稍微進(jìn)階一下，我們從兩側(cè)開始，選出最小和最大，從而進(jìn)行交換，雖然沒有提高多少效率，但是還是比之前的速度快兩倍

直接選擇排序注意事項(xiàng)

1，這里begin和end都是外層循環(huán)，也就是隨著++和--進(jìn)行縮小差距

2，這里begin和end不是索引，而是縮小差距用的

3，這里是mini和maxi是索引

4，最后交換的時(shí)候交換的是下標(biāo)的元素，不是下標(biāo)

直接選擇排序多趟實(shí)現(xiàn)圖解

直接選擇排序代碼實(shí)現(xiàn)

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//直接選擇排序
void SelectSort(int* a, int n)
{//多趟循環(huán)int begin = 0, end = n - 1;while (begin < end){//單趟循環(huán)，找出最小值和最大值int mini = begin, maxi = end;for (int i = begin; i <= end; i++){//找到最小值，賦值下標(biāo)if (a[i] < a[mini]){mini = i;}//找到最小值，賦值下標(biāo)if (a[i] > a[maxi]){maxi = i;}}//把最小值和最大值放到開頭和結(jié)尾去Swap(&a[mini], &a[begin]);Swap(&a[maxi], &a[end]);begin++; end--;}
}

解釋：

• 外層循環(huán)從索引0開始，直到倒數(shù)第二個(gè)元素。
• 在每次外層循環(huán)中，假設(shè)當(dāng)前索引位置的元素是未排序部分的最小值。
• 內(nèi)層循環(huán)從外層循環(huán)的下一個(gè)位置開始，遍歷未排序部分的元素，尋找最小值的索引minIndex。
• 如果找到的最小值不在當(dāng)前索引位置，使用Swap函數(shù)將其交換到當(dāng)前索引位置。
• 這樣，每次外層循環(huán)結(jié)束時(shí)，未排序部分的最小值都被移動(dòng)到了排序好的部分的末尾。

注意：

• 直接選擇排序不是穩(wěn)定的排序算法，即相等元素之間的相對(duì)順序可能會(huì)改變。
• 直接選擇排序的時(shí)間復(fù)雜度是O(n^2)，在大多數(shù)情況下，它不如其他更高效的排序算法。
• 直接選擇排序的空間復(fù)雜度是O(1)，因?yàn)樗窃嘏判蛩惴ā?/li>

選擇排序時(shí)間復(fù)雜度計(jì)算

1. 外層循環(huán)：選擇排序算法有一個(gè)外層循環(huán)，它從第一個(gè)元素遍歷到倒數(shù)第二個(gè)元素。這個(gè)循環(huán)執(zhí)行了 n?1 次，其中 n 是數(shù)組的長度。

2. 內(nèi)層循環(huán)：對(duì)于外層循環(huán)的每一次迭代，都有一個(gè)內(nèi)層循環(huán)，它從當(dāng)前考慮的元素之后的第一個(gè)元素遍歷到數(shù)組的最后一個(gè)元素。在第一次外層循環(huán)迭代時(shí)，內(nèi)層循環(huán)執(zhí)行 n?1 次；在第二次迭代時(shí)，執(zhí)行n?2 次；依此類推，直到最后一次迭代，只執(zhí)行一次。

3. 總迭代次數(shù)：內(nèi)層循環(huán)的總迭代次數(shù)可以表示為一個(gè)等差數(shù)列之和： (𝑛?1)+(𝑛?2)+…+2+1=n(n?1)?/2

4. 時(shí)間復(fù)雜度：由于外層循環(huán)和內(nèi)層循環(huán)的迭代次數(shù)都是 Θ(𝑛)（即線性關(guān)系），因此選擇排序的總時(shí)間復(fù)雜度是 Θ(𝑛^2)。

5. 空間復(fù)雜度：選擇排序是原地排序算法，它只需要一個(gè)額外的變量來存儲(chǔ)最小元素的索引，因此空間復(fù)雜度是 Θ(1)。

插入排序

前言

插入排序是很重要的排序，著名的希爾排序就是從插入排序演變過來的，所以我們需要并且很多時(shí)候有些面試也是會(huì)面試插入排序的，所以需要好好捋清楚插入排序的邏輯是什么

插入排序gif

插入排序單趟實(shí)現(xiàn)

1，插入排序我們需要假設(shè)最后一個(gè)數(shù)值也就是end+1是需要排序的，其他都是排序好的

2，把end+1這個(gè)下標(biāo)的數(shù)值存放在tmp里面，并且和前面進(jìn)行比較

3，如果遇見的元素比tmp大，我們繼續(xù)往前移動(dòng)進(jìn)行比較，同時(shí)a[end]=a[end+1]往后覆蓋

4，當(dāng)遇見的是比tmp小的數(shù)值的時(shí)候，此時(shí)我們找到了tmp數(shù)值應(yīng)該在的位置，進(jìn)行插入

插入排序注意事項(xiàng)

這里需要注意的關(guān)鍵也是區(qū)間問題，假設(shè)數(shù)組有n個(gè)，那么end就是倒數(shù)第二個(gè)下標(biāo)，end+1就是最后一個(gè)下標(biāo)，是為了防止越界

我們需要小于n-1，因?yàn)?#xff0c;end=n-1；end+1=n，那么就越界了

所以在循環(huán)最大值里面，end=i=n-2,；end+1=n-1（最后一個(gè)數(shù)值）

插入排序代碼的實(shí)現(xiàn)

//插入排序
void InsertionSort(int* a, int n)
{//多趟實(shí)現(xiàn),這里n的截止條件-1，是因?yàn)橄聵?biāo)從n-1就結(jié)束了，//不過我們需要小于n-1，因?yàn)?#xff0c;end=n-1；end+1=n，那么就越界了for (int i = 0; i < n - 1; i++){//單趟實(shí)現(xiàn)int end = i; int tmp = a[end + 1];while (end >= 0){//判斷是不是比前一個(gè)數(shù)值小，小的話就往前走，不小的話停下來進(jìn)行賦值if (tmp < a[end]){a[end + 1] = a[end];end--;}else//找到了，此時(shí)跳出循環(huán)就可以{break;}}//這里是很多人會(huì)搞混亂的一點(diǎn)，//因?yàn)槭钦业搅?#xff0c;所以end還沒有繼續(xù)移動(dòng)，但是end+1+1的元素已經(jīng)移動(dòng)，所以end+1的位置是tmp應(yīng)該出現(xiàn)的位置a[end + 1] = tmp;}
}

解釋：

1. 函數(shù)InsertionSort接受兩個(gè)參數(shù)：一個(gè)指向整數(shù)數(shù)組a的指針和數(shù)組的長度n。

2. 外層循環(huán)從索引0遍歷到n-1。每次迭代，i代表已排序部分的最后一個(gè)元素的索引。

3. 在外層循環(huán)的每次迭代中，end變量被設(shè)置為當(dāng)前索引i，表示當(dāng)前考慮的元素的索引。tmp變量存儲(chǔ)了a[i + 1]的值，這是未排序的第一個(gè)元素，也是我們準(zhǔn)備插入到已排序部分的元素。

4. 內(nèi)層while循環(huán)用于在已排序部分從后向前掃描，找到tmp應(yīng)該插入的位置。end變量隨著比較逐步遞減。

5. 在while循環(huán)中，如果tmp小于當(dāng)前比較的元素a[end]，則將a[end]向后移動(dòng)一個(gè)位置，為tmp騰出空間。

6. 如果tmp大于或等于a[end]，則while循環(huán)通過break語句結(jié)束，找到了tmp應(yīng)該插入的位置。

7. 循環(huán)結(jié)束后，將tmp賦值給a[end + 1]，完成插入操作。

8. 這個(gè)過程重復(fù)進(jìn)行，直到數(shù)組中的所有元素都被掃描并插入到正確的位置。

代碼邏輯：

• 插入排序的基本思想是，對(duì)于數(shù)組中的每個(gè)元素，將其插入到前面已經(jīng)排好序的子數(shù)組中的正確位置。
• 初始時(shí)，認(rèn)為數(shù)組的第一個(gè)元素是已排序的。然后，從第二個(gè)元素開始，逐個(gè)插入到前面的已排序序列中。
• 每次插入操作都需要將元素與已排序序列中的元素進(jìn)行比較，直到找到合適的插入點(diǎn)。

注意：

• 這段代碼在插入元素時(shí)，如果插入點(diǎn)是數(shù)組的開始，那么不需要進(jìn)行任何移動(dòng)操作，直接插入即可。
• 代碼中的end變量用于記錄當(dāng)前比較的元素在數(shù)組中的位置，而tmp變量用于暫存當(dāng)前要插入的元素。
• 插入排序是穩(wěn)定的排序算法，因?yàn)樗粫?huì)改變相等元素的相對(duì)順序。

性能：

• 插入排序的平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是?𝑂(𝑛^2)，其中?n?是數(shù)組的長度。
• 插入排序的空間復(fù)雜度是?𝑂(1)，因?yàn)樗窃嘏判蛩惴?#xff0c;不需要額外的存儲(chǔ)空間。

插入排序的時(shí)間復(fù)雜度

插入排序算法的時(shí)間復(fù)雜度取決于數(shù)組的初始順序，具體如下：

1. 最佳情況：如果輸入數(shù)組已經(jīng)是完全有序的，插入排序只需要進(jìn)行 n 次比較（每次比較后插入一個(gè)元素到已排序部分），而不需要進(jìn)行任何交換。在這種情況下，時(shí)間復(fù)雜度是O(n)。

2. 平均情況：在平均情況下，插入排序的時(shí)間復(fù)雜度是 O(n^2)。這是因?yàn)槊總€(gè)元素都需要與已排序部分的多個(gè)元素進(jìn)行比較，平均下來，每個(gè)元素需要比較n/2次。

3. 最壞情況：如果輸入數(shù)組是完全逆序的，插入排序需要進(jìn)行n(n?1)?/2次比較和 n(n?1)?/2次交換，時(shí)間復(fù)雜度是 O(n^2)。

4. 空間復(fù)雜度：插入排序是原地排序算法，它只需要一個(gè)額外的存儲(chǔ)空間來暫存當(dāng)前比較的元素，因此空間復(fù)雜度是 O(1)。

5. 穩(wěn)定性：插入排序是穩(wěn)定的排序算法，它保持了相等元素的原始順序。

時(shí)間復(fù)雜度的詳細(xì)分析：

• 插入排序通過構(gòu)建有序序列來工作，對(duì)于未排序的數(shù)據(jù)，在已排序的序列中從后向前掃描，找到相應(yīng)位置并插入。
• 在每次迭代中，算法將當(dāng)前元素與已排序序列中的元素逐一比較，找到合適的插入點(diǎn)。
• 對(duì)于每個(gè)元素，比較操作可能需要進(jìn)行?i?次（其中?𝑖i?是當(dāng)前元素在數(shù)組中的位置），從第一個(gè)元素到最后一個(gè)元素，所需比較的總次數(shù)是遞增的。

時(shí)間復(fù)雜度的數(shù)學(xué)表達(dá)式是：

總比較次數(shù)=1+2+3+…+(𝑛?1)=𝑛(𝑛?1)/2總比較次數(shù)

這表明插入排序的時(shí)間復(fù)雜度是 Θ(𝑛^2),盡管在最壞情況下時(shí)間復(fù)雜度較高，插入排序?qū)τ谛∫?guī)模數(shù)據(jù)集或部分有序的數(shù)據(jù)集來說是非常高效的。

希爾排序

前言

從希爾開始，排序的速度就開始上升了，這里的排序開始上一個(gè)難度了，當(dāng)然難一點(diǎn)的排序其實(shí)也不是很難，當(dāng)你對(duì)于插入排序了解的足夠深入的時(shí)候，你會(huì)發(fā)現(xiàn)其實(shí)希爾就是插入的異形，但是本質(zhì)上還是一樣的

希爾排序gif

希爾排序單趟實(shí)現(xiàn)

1，希爾排序本質(zhì)就是插入排序的進(jìn)化，插入排序是尋找比較進(jìn)行插入，希爾這個(gè)人覺得插入排序有點(diǎn)慢，就覺得我們可不可以進(jìn)行預(yù)排序，也就是數(shù)值原來是0-9的情況下，最壞的情況我們需要循環(huán)9次數(shù)才能找到需要插入的點(diǎn)在哪，那么此時(shí)我們能不能進(jìn)行一個(gè)預(yù)排序

2，所謂的預(yù)排序就是，我們假設(shè)幾個(gè)為一組，幾個(gè)為一組，這個(gè)組的變量我們?cè)O(shè)置為gap。假設(shè)處置3個(gè)為一組，那么gap=3

3，此時(shí)我們可以把這一組，先采取插入排序的方式進(jìn)行預(yù)排序，預(yù)排序之后我們就會(huì)發(fā)現(xiàn)這一組的這條線上的數(shù)值已經(jīng)有序

4，多趟實(shí)現(xiàn)只是反復(fù)的實(shí)現(xiàn)第一趟的實(shí)現(xiàn)的邏輯

希爾排序的多趟實(shí)現(xiàn)

1，多趟實(shí)現(xiàn)只是反復(fù)的實(shí)現(xiàn)第一趟的實(shí)現(xiàn)的邏輯

2，我們需要先知道單趟遍歷的時(shí)候，我們需要假設(shè)gap一組的，這個(gè)中間的元素是沒有的，那么此時(shí)此時(shí)一組就是兩個(gè)數(shù)值，我們需要讓這兩個(gè)數(shù)值進(jìn)行交換

3，這兩個(gè)數(shù)值交換之后我們這個(gè)時(shí)候需要循環(huán)開始插入排序的邏輯，也就是假設(shè)前面的兩個(gè)數(shù)值是已經(jīng)有序的，那么新插入的一個(gè)數(shù)值是需要排序的，我們進(jìn)行排序

4，一趟結(jié)束之后，我們繼續(xù)多趟實(shí)現(xiàn)，這幾個(gè)數(shù)值繼續(xù)預(yù)排序

5，繼續(xù)預(yù)排序

6，此時(shí)gap=3，那么我們繼續(xù)，gap/2=1，之后繼續(xù)進(jìn)行預(yù)排序，此時(shí)我們就得到了這個(gè)排序正確的數(shù)值

希爾排序代碼的實(shí)現(xiàn)-版本1

//希爾排序
void ShellSort(int* a, int n)
{int gap = n - 1;//定義gap,這里循環(huán)停止的條件是>1，原因是+1了，已經(jīng)恒大于0了，所以需要大于1，等于都不可以while (gap > 1){gap = gap / 3 + 1;//循環(huán)實(shí)現(xiàn)每一組for (int j = 0; j < gap; j++){//gap單趟實(shí)現(xiàn)for (int i = j; i < n - gap; i += gap){int end = i; int tmp = a[end + gap];//一組的實(shí)現(xiàn)while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//交換找到的數(shù)值a[end + gap] = tmp;}}}
}

?解釋：

1. 函數(shù)ShellSort接受兩個(gè)參數(shù)：一個(gè)指向整數(shù)數(shù)組a的指針和數(shù)組的長度n。

2. 初始化間隔gap為數(shù)組長度n - 1，這是希爾排序開始時(shí)的最大間隔。

3. while循環(huán)用于逐步減小間隔，直到間隔為1。當(dāng)gap大于1時(shí)，循環(huán)繼續(xù)。

4. 在每次while循環(huán)的開始，重新計(jì)算間隔gap。這里使用的是gap = gap / 3 + 1，這是一種常見的間隔序列，由Donald Shell提出。

5. 外層for循環(huán)用于遍歷數(shù)組，步長為當(dāng)前的間隔gap。

6. 內(nèi)層for循環(huán)用于實(shí)現(xiàn)插入排序，但僅限于間隔gap內(nèi)的范圍。

7. 在內(nèi)層循環(huán)中，end變量記錄當(dāng)前考慮的元素的索引，tmp變量暫存當(dāng)前要插入的元素。

8. while循環(huán)用于在間隔gap內(nèi)從后向前掃描，找到tmp應(yīng)該插入的位置。

9. 如果tmp小于當(dāng)前比較的元素a[end]，則將a[end]向后移動(dòng)一個(gè)間隔gap的距離，為tmp騰出空間。

10. 如果tmp大于或等于a[end]，則while循環(huán)結(jié)束，找到了tmp應(yīng)該插入的位置。

11. 循環(huán)結(jié)束后，將tmp賦值給a[end + gap]，完成插入操作。

12. 這個(gè)過程重復(fù)進(jìn)行，直到數(shù)組中的所有元素都被掃描并插入到正確的位置。

代碼邏輯：

• 希爾排序通過多個(gè)插入排序的變體來工作，每個(gè)變體都有一個(gè)特定的間隔。
• 初始時(shí)，間隔較大，排序的穩(wěn)定性較差，但可以快速減少無序度。
• 隨著間隔逐漸減小，排序的穩(wěn)定性逐漸提高，最終當(dāng)間隔為1時(shí)，算法變?yōu)槠胀ǖ牟迦肱判?#xff0c;確保數(shù)組完全有序。

注意：

• 希爾排序不是穩(wěn)定的排序算法，因?yàn)樗赡軙?huì)改變相等元素的相對(duì)順序。
• 希爾排序的時(shí)間復(fù)雜度通常在?𝑂(𝑛log?𝑛) 和?𝑂(𝑛^2)?之間，具體取決于間隔序列的選擇。
• 希爾排序的空間復(fù)雜度是?𝑂(1，因?yàn)樗窃嘏判蛩惴?#xff0c;不需要額外的存儲(chǔ)空間。

希爾排序代碼的實(shí)現(xiàn)-版本2

上面那個(gè)代碼一般是教學(xué)使用，書寫會(huì)更加詳細(xì)理解，但是很多書本會(huì)這樣寫

這里的關(guān)鍵在于，不再進(jìn)行先一組排序結(jié)束，再反過來進(jìn)行下一組反復(fù)執(zhí)行

而是直接這一組實(shí)現(xiàn)完畢之后，++，直接進(jìn)行下一組的實(shí)現(xiàn)，本質(zhì)上還是一樣的

只是直接這樣書寫，容易不理解

//希爾排序
void ShellSort02(int* a, int n)
{int gap = n - 1;//定義gap,這里循環(huán)停止的條件是>1，原因是+1了，已經(jīng)恒大于0了，所以需要大于1，等于都不可以while (gap > 1){gap = gap / 3 + 1;//循環(huán)實(shí)現(xiàn)每一組+//gap單趟實(shí)現(xiàn)for (int i = 0; i < n - gap; i++){int end = i; int tmp = a[end + gap];//一組的實(shí)現(xiàn)while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//交換找到的數(shù)值a[end + gap] = tmp;}}
}

解釋：

1. 函數(shù)ShellSort02接受兩個(gè)參數(shù)：一個(gè)指向整數(shù)數(shù)組a的指針和數(shù)組的長度n。

2. 初始化間隔gap為數(shù)組的最后一個(gè)索引n - 1。

3. while循環(huán)用于逐步減小間隔，直到間隔小于或等于1。循環(huán)的條件是gap > 1，這是因?yàn)殚g隔在每次迭代中都會(huì)減小，所以不需要檢查gap == 1的情況。

4. 在while循環(huán)內(nèi)部，重新計(jì)算間隔gap。這里使用的計(jì)算方法是gap = gap / 3 + 1，這是一種常見的間隔序列，旨在逐步減小間隔，直到達(dá)到1。

5. 外層for循環(huán)遍歷數(shù)組，直到i < n - gap，即遍歷到數(shù)組的末尾減去當(dāng)前間隔的位置。

6. 在外層for循環(huán)中，end變量記錄當(dāng)前考慮的元素的索引，tmp變量暫存當(dāng)前間隔位置的元素值。

7. 內(nèi)層while循環(huán)用于在數(shù)組中找到tmp應(yīng)該插入的位置。它從當(dāng)前索引end開始，向前以間隔gap的距離進(jìn)行比較。

8. 如果tmp小于當(dāng)前比較的元素a[end]，則將a[end]向后移動(dòng)一個(gè)間隔gap的距離，為tmp騰出空間。

9. 如果tmp大于或等于a[end]，則while循環(huán)結(jié)束，找到了tmp應(yīng)該插入的位置。

10. 循環(huán)結(jié)束后，將tmp賦值給a[end + gap]，完成插入操作。

11. 這個(gè)過程重復(fù)進(jìn)行，直到數(shù)組中的所有元素都被掃描并插入到正確的位置。

代碼邏輯：

• 希爾排序通過多個(gè)插入排序的變體來工作，每個(gè)變體都有一個(gè)特定的間隔。
• 初始時(shí)，間隔較大，隨著算法的進(jìn)行，間隔逐漸減小，直到變?yōu)?，此時(shí)算法變?yōu)槠胀ǖ牟迦肱判颉?/li>
• 通過逐步減小間隔，希爾排序能夠在每次迭代中對(duì)數(shù)組的更大范圍內(nèi)的元素進(jìn)行排序，從而減少比較和移動(dòng)的次數(shù)。

希爾排序gap的界定

一般來說，一組為多少這個(gè)不好說，希爾開始書寫的時(shí)候，gap是/2,來進(jìn)行書寫的，但是被認(rèn)為效率最高的是，除以3+1，但是/3+1有一個(gè)弊端就是這個(gè)是恒大于0的，所以終止條件應(yīng)該換為大于1就繼續(xù)循環(huán)，小于等于1就停止循環(huán)

希爾排序的時(shí)間復(fù)雜度

希爾排序的時(shí)間復(fù)雜度取決于所選擇的間隔序列，它通常介于以下范圍：

1. 最好情況：對(duì)于某些特定的間隔序列，希爾排序可以達(dá)到O(nlogn) 的時(shí)間復(fù)雜度，這與快速排序或歸并排序相當(dāng)。

2. 平均情況：平均情況下，希爾排序的時(shí)間復(fù)雜度通常被認(rèn)為是 O(n(logn)2)，這比=O(nlogn) 稍差，但仍然比普通插入排序的 𝑂(𝑛^2) 好得多。

3. 最壞情況：最壞情況下，希爾排序的時(shí)間復(fù)雜度可以退化到𝑂(𝑛^2)，這通常發(fā)生在間隔序列選擇不佳時(shí)。

4. 實(shí)際性能：在實(shí)際應(yīng)用中，希爾排序的性能通常比普通插入排序好，但不如快速排序、堆排序或歸并排序。它的實(shí)際性能還取決于數(shù)據(jù)的初始狀態(tài)和間隔序列的選擇。

5. 間隔序列的影響：不同的間隔序列對(duì)希爾排序的性能有很大影響。例如，使用Hibbard 間隔序列或Sedgewick間隔序列可以提高性能，有時(shí)甚至可以達(dá)到接近 O(nlogn) 的效率。

6. 空間復(fù)雜度：希爾排序是原地排序算法，其空間復(fù)雜度為 𝑂(1)。

7. 穩(wěn)定性：希爾排序不是穩(wěn)定的排序算法，這意味著相等的元素在排序后可能會(huì)改變它們?cè)瓉淼捻樞颉?/p>

總的來說，希爾排序是一種有效的排序算法，特別是對(duì)于中等大小的數(shù)據(jù)集或者當(dāng)數(shù)據(jù)已經(jīng)部分有序時(shí)。然而，對(duì)于大型數(shù)據(jù)集，通常推薦使用其他更高效的排序算法，如快速排序、堆排序或歸并排序。

快排（霍爾版本-遞歸解決）

前言

快排是很重要的排序，也是一種比較難以理解的排序，這里我們會(huì)用遞歸的方式和非遞歸的方式來解決，遞歸來解決是比較簡(jiǎn)單的，非遞歸來解決是有點(diǎn)難度的

快排也稱之為霍爾排序，因?yàn)榘l(fā)明者是霍爾，本來是命名為霍爾排序的，但是霍爾這個(gè)人對(duì)于自己創(chuàng)造的排序很自信，所以命名為快排

當(dāng)然也是如他所料，快排確實(shí)很快，但是還沒有達(dá)到第一批次那個(gè)程度

快排gif

快排實(shí)現(xiàn)邏輯排序

單趟實(shí)現(xiàn)邏輯:
1.假設(shè)左邊為keyi，也就是對(duì)比數(shù)值
2，右邊R先走，循環(huán)尋找比keyi小的數(shù)值
3，左邊l走，循環(huán)尋找比keyi大的數(shù)值
4，交換找到的比keyi大的數(shù)值和小的數(shù)值，此時(shí)會(huì)導(dǎo)致小的在左邊，大的在右邊，最后相遇的時(shí)候交換keyi和相遇的元素

多趟實(shí)現(xiàn):
1，多趟實(shí)現(xiàn)可以采取遞歸和非遞歸，但是總體邏輯都是一樣的，這里先講解一下遞歸的方式2，此時(shí)，我們會(huì)發(fā)現(xiàn)keyi下標(biāo)所在位置，就是從前往后6，的位置，所以6回到自己的位置，我們以keyi為分界點(diǎn)進(jìn)行切割【left,keyi-1】keyi【keyi+1,right】
進(jìn)行遞歸，從而實(shí)現(xiàn)簡(jiǎn)易版的速排
完善邏輯:
1，此時(shí)是快排還是有點(diǎn)問題的，當(dāng)數(shù)值本身就是順序的時(shí)候
會(huì)發(fā)現(xiàn)此時(shí)的時(shí)間復(fù)雜度就變成了n^2，也就是不快了
2，原因是當(dāng)本身就是排序好的時(shí)候，right右邊會(huì)一直往左邊尋
找，直到找到left，和自己交換，此時(shí)的時(shí)間復(fù)雜度也就是
n,n-1..1.0
3，解決辦法，我們可以三個(gè)數(shù)值取中，什么意思?也就是不管什么情況，我們都取出前三個(gè)數(shù)值，比如這里的
6 1 2
我們?nèi)〕? 1 2，取出中間的位置，2，和keyi進(jìn)行交換其他邏輯不變
完善邏輯:
1，此時(shí)我們發(fā)現(xiàn)邏輯沒有問題，但是速度還是和堆排序有點(diǎn)差距，那么此時(shí)我們繼續(xù)進(jìn)行優(yōu)化
2，因?yàn)檫@里是用遞歸來實(shí)現(xiàn)的，我們發(fā)現(xiàn)，遞歸的實(shí)現(xiàn)是逐級(jí)實(shí)現(xiàn)的，也就是
第-層->第n層:1->2->3->4->…->n-1->n
這樣的遞歸方式來實(shí)現(xiàn)的，所以越到下面，遞歸的越多
我們可以把最后十層的遞歸用插入排序來實(shí)現(xiàn)一下，
3，為什么用插入排序?在排序里面有希爾排序，冒泡排序，選
擇排序，堆排序
希爾排序->插入排序的進(jìn)階(書寫復(fù)雜)
冒泡排序->時(shí)間復(fù)雜度高
選擇排序->時(shí)間復(fù)雜度和冒泡一樣，比較高
堆排序->處理大型數(shù)字問題，這里沒必要
所以我們采取插入排序的方式進(jìn)行解決
4，解決，我們只需要在遞歸的時(shí)候加一個(gè)判斷，就可以，當(dāng)數(shù)
值小于等于10 的時(shí)候，我們直接調(diào)用插入排序解決問題。
此時(shí)速排(霍爾排序)，遞歸的方式也就結(jié)束了。

圖解：

快排單趟實(shí)現(xiàn)

快排多趟實(shí)現(xiàn)

簡(jiǎn)易版本的代碼實(shí)現(xiàn)

//霍爾方法(遞歸實(shí)現(xiàn))
void QuickSort01(int* a, int left, int right)
{//遞歸停止條件if (left >= right)return;//單趟實(shí)現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動(dòng),是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動(dòng)，是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實(shí)現(xiàn)//[left,keyi-1] keyi [keyi+1,right]   這里傳遞的是區(qū)間//  1     0      1     2      1       當(dāng)只剩一個(gè)數(shù)值的時(shí)候，也就是這個(gè)區(qū)間的時(shí)候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right);
}

解釋：

1. 函數(shù)定義：QuickSort01函數(shù)接受一個(gè)整數(shù)數(shù)組的指針a以及兩個(gè)整數(shù)left和right，分別表示要排序的數(shù)組部分的起始和結(jié)束索引。

2. 遞歸終止條件：如果left大于或等于right，則當(dāng)前子數(shù)組無需排序，遞歸結(jié)束。

3. 初始化：設(shè)置兩個(gè)指針begin和end分別指向子數(shù)組的起始和結(jié)束位置，keyi作為基準(zhǔn)元素的索引，初始位置設(shè)為left。

4. 單趟排序：

   • 使用兩個(gè)內(nèi)層循環(huán)，一個(gè)從右側(cè)向左尋找比基準(zhǔn)值小的元素，另一個(gè)從左側(cè)向右尋找比基準(zhǔn)值大的元素。
   • 當(dāng)找到合適的元素時(shí)，交換這兩個(gè)元素的位置，然后繼續(xù)尋找，直到begin和end相遇。

5. 基準(zhǔn)值定位：將基準(zhǔn)值a[keyi]與begin指向的元素交換，此時(shí)begin指向的位置是基準(zhǔn)值的最終位置。

6. 遞歸排序：對(duì)基準(zhǔn)值左邊的子數(shù)組[left, keyi - 1]和右邊的子數(shù)組[keyi + 1, right]遞歸調(diào)用QuickSort01函數(shù)進(jìn)行排序。

7. 效率：快速排序的平均時(shí)間復(fù)雜度為O(n log n)，但在最壞情況下（如數(shù)組已經(jīng)排序）時(shí)間復(fù)雜度會(huì)退化到O(n^2)。霍爾方法通過減少不必要的數(shù)據(jù)交換來提高排序效率。

8. 輔助函數(shù)：Swap函數(shù)用于交換兩個(gè)元素的值，雖然在代碼中未給出定義，但它是快速排序中交換元素的關(guān)鍵操作。

快速排序算法的效率和性能在實(shí)際應(yīng)用中通常優(yōu)于其他O(n log n)算法，如歸并排序，尤其是在數(shù)據(jù)量較大時(shí)。然而，其穩(wěn)定性不如歸并排序，且在最壞情況下性能較差。在實(shí)際應(yīng)用中，快速排序通常與其他排序算法結(jié)合使用，以提高整體排序性能。

注意事項(xiàng)

注意事項(xiàng)1

這里有一個(gè)關(guān)鍵點(diǎn)是很重要的，也就是我們是從右邊先出發(fā)的，因?yàn)槲覀兊膋eyi的位置在左邊。

如果我們的keyi的下標(biāo)在左邊，并且左邊先走的話，就會(huì)產(chǎn)生一種結(jié)果

如圖

注意事項(xiàng)2

不是等于就交換，是等于會(huì)跳過往下找

當(dāng)我們寫的是不等于的時(shí)候

快排完整代碼實(shí)現(xiàn)-（三數(shù)值取中）

此時(shí)存在的最大問題就是如果排序本身就是順序排序的情況下，這時(shí)間復(fù)雜度反而高了，所以我們對(duì)排序進(jìn)行修改

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//霍爾方法(遞歸實(shí)現(xiàn))
//三數(shù)取中
int GetMid(int* a, int left, int right)
{//三數(shù)取中傳參的是下標(biāo)，我們?nèi)≈幸彩歉鶕?jù)下標(biāo)進(jìn)行計(jì)算的int mid = (left + right) / 2;if (a[left] < a[right]){if (a[mid] < a[left])//a[mid] < a[left] < a[right]{return left;}else if(a[mid] > a[right])// a[left] < a[right] < a[mid] {return right;}else{return mid;}}else//a[left] > a[right]{if (a[mid] > a[left])//a[mid] > a[left] > a[right]{return left;}else if (a[mid] < a[right])//a[left] > a[right] > a[mid] {return right;}else{return mid;}}
}
void QuickSort01(int* a, int left, int right)
{//遞歸停止條件if (left >= right)return;//三數(shù)取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實(shí)現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動(dòng),是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動(dòng)，是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實(shí)現(xiàn)//[left,keyi-1] keyi [keyi+1,right]   這里傳遞的是區(qū)間//  1     0      1     2      1       當(dāng)只剩一個(gè)數(shù)值的時(shí)候，也就是這個(gè)區(qū)間的時(shí)候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right);
}

總結(jié)：

1. 函數(shù)目的：選擇一個(gè)合適的基準(zhǔn)值，以提高快速排序算法的效率。

2. 傳入?yún)?shù)：接受一個(gè)整數(shù)數(shù)組的指針a，以及表示數(shù)組部分邊界的整數(shù)left和right。

3. 計(jì)算中間索引：通過(left + right) / 2計(jì)算中間元素的索引mid。

4. 三數(shù)取中邏輯：

   • 如果數(shù)組的第一個(gè)元素a[left]小于最后一個(gè)元素a[right]：
     • 如果中間元素a[mid]小于第一個(gè)元素，則選擇第一個(gè)元素作為基準(zhǔn)。
     • 如果中間元素大于最后一個(gè)元素，則選擇最后一個(gè)元素作為基準(zhǔn)。
     • 否則，選擇中間元素作為基準(zhǔn)。
   • 如果第一個(gè)元素大于或等于最后一個(gè)元素（即數(shù)組首尾元素已經(jīng)排序或相等）：
     • 如果中間元素大于第一個(gè)元素，則選擇第一個(gè)元素作為基準(zhǔn)。
     • 如果中間元素小于最后一個(gè)元素，則選擇最后一個(gè)元素作為基準(zhǔn)。
     • 否則，選擇中間元素作為基準(zhǔn)。

5. 返回值：函數(shù)返回基準(zhǔn)值的索引。

6. 優(yōu)化目的：通過三數(shù)取中法選擇基準(zhǔn)，可以減少快速排序在特定情況下性能退化的問題，如數(shù)組已經(jīng)排序或包含大量重復(fù)元素。

7. 適用場(chǎng)景：適用于快速排序算法中，作為選擇基準(zhǔn)值的策略。

8. 性能影響：選擇一個(gè)好的基準(zhǔn)值可以確保數(shù)組被均勻地劃分，從而接近快速排序的最佳平均時(shí)間復(fù)雜度O(n log n)。

三數(shù)取中法是一種簡(jiǎn)單而有效的基準(zhǔn)選擇策略，它通過比較數(shù)組的首元素、尾元素和中間元素，來確定一個(gè)相對(duì)平衡的基準(zhǔn)值，有助于提高快速排序的整體性能和穩(wěn)定性。

快排完整代碼實(shí)現(xiàn)-（減少遞歸次數(shù)）

此時(shí)我們還面臨的問題就是底層的遞歸次數(shù)過多的問題，遞歸會(huì)隨著次數(shù)的增加呈現(xiàn)倍數(shù)增長，就像三角形一樣

最后我們減少遞歸次數(shù)，把最底層從遞歸改為插入排序，邏輯完成

快排完整代碼

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//霍爾方法(遞歸實(shí)現(xiàn))
//三數(shù)取中
int GetMid(int* a, int left, int right)
{//三數(shù)取中傳參的是下標(biāo)，我們?nèi)≈幸彩歉鶕?jù)下標(biāo)進(jìn)行計(jì)算的int mid = (left + right) / 2;if (a[left] < a[right]){if (a[mid] < a[left])//a[mid] < a[left] < a[right]{return left;}else if(a[mid] > a[right])// a[left] < a[right] < a[mid] {return right;}else{return mid;}}else//a[left] > a[right]{if (a[mid] > a[left])//a[mid] > a[left] > a[right]{return left;}else if (a[mid] < a[right])//a[left] > a[right] > a[mid] {return right;}else{return mid;}}
}
void QuickSort01(int* a, int left, int right)
{//遞歸停止條件if (left >= right)return;//當(dāng)區(qū)間數(shù)值小于10個(gè)，此時(shí)我們直接采取插入排序進(jìn)行排序if (right - left + 1 <= 10){//這里記得是左右區(qū)間，所以不能只傳遞a，而是傳遞a + leftInsertionSort(a + left, right - left + 1);}else{//三數(shù)取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實(shí)現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動(dòng),是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動(dòng)，是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實(shí)現(xiàn)//[left,keyi-1] keyi [keyi+1,right]   這里傳遞的是區(qū)間//  1     0      1     2      1       當(dāng)只剩一個(gè)數(shù)值的時(shí)候，也就是這個(gè)區(qū)間的時(shí)候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right);}
}

代碼解釋：

1. 三數(shù)取中函數(shù) GetMid:

   • 計(jì)算中間索引?mid。
   • 通過比較數(shù)組的首元素、尾元素和中間元素，選擇一個(gè)合適的基準(zhǔn)值。
   • 如果首元素小于尾元素，選擇中間元素和首尾元素中較小或較大的一個(gè)作為基準(zhǔn)。
   • 如果首元素大于尾元素，選擇中間元素和首尾元素中較大或較小的一個(gè)作為基準(zhǔn)。

2. 快速排序函數(shù) QuickSort01:

   • 遞歸停止條件：如果當(dāng)前區(qū)間的左右索引?left?和?right?交叉或重合，則不需要排序。
   • 當(dāng)區(qū)間大小小于或等于10時(shí)，使用插入排序，因?yàn)樾?shù)組上插入排序更高效。
   • 使用?GetMid?函數(shù)獲取基準(zhǔn)值的索引，并將基準(zhǔn)值與首元素交換。
   • 霍爾方法的分區(qū)操作，通過兩個(gè)指針?begin?和?end?進(jìn)行分區(qū)。
   • 遞歸地對(duì)基準(zhǔn)值左邊和右邊的子區(qū)間進(jìn)行快速排序。

3. 輔助函數(shù) Swap:

   • 交換兩個(gè)元素的值，雖然代碼中未給出定義，但通常是一個(gè)簡(jiǎn)單的值交換操作。

總結(jié)：

• 算法優(yōu)化: 通過三數(shù)取中法選擇基準(zhǔn)值，可以提高基準(zhǔn)值的選中質(zhì)量，從而提高快速排序的效率。
• 小數(shù)組優(yōu)化: 當(dāng)子數(shù)組的大小，小于或等于10時(shí)，使用插入排序代替快速排序，因?yàn)樾?shù)組上插入排序的性能通常更好。
• 遞歸與迭代: 快速排序是一個(gè)遞歸算法，但在小數(shù)組上切換到迭代的插入排序可以減少遞歸開銷。
• 分區(qū)策略: 使用霍爾方法進(jìn)行分區(qū)，這是一種高效的分區(qū)策略，可以減少不必要的數(shù)據(jù)交換。
• 適用場(chǎng)景: 這種改進(jìn)的快速排序適用于大多數(shù)需要排序的場(chǎng)景，尤其是在大數(shù)據(jù)集上，它能夠保持較好的性能。
• 時(shí)間復(fù)雜度: 平均情況下時(shí)間復(fù)雜度為 O(n log n)，最壞情況下（已排序數(shù)組）時(shí)間復(fù)雜度為 O(n^2)，但由于三數(shù)取中法和插入排序的結(jié)合，最壞情況出現(xiàn)的概率降低。

通過這種改進(jìn)，快速排序算法在處理小數(shù)組時(shí)更加高效，同時(shí)在大數(shù)據(jù)集上也能保持較好的性能，使其成為一種更加健壯的排序算法。

快排的時(shí)間復(fù)雜度

快速排序算法的時(shí)間復(fù)雜度取決于分區(qū)過程中基準(zhǔn)值的選擇。

理想情況下

基準(zhǔn)值會(huì)將數(shù)組均勻地分成兩部分，每部分的元素?cái)?shù)量大致相等。對(duì)于這種理想情況，快速排序的時(shí)間復(fù)雜度是 O(n log n)，其中 n 是數(shù)組中的元素?cái)?shù)量。

最壞情況下

如果基準(zhǔn)值的選擇非常不均勻，從而導(dǎo)致每次分區(qū)都極不平衡，快速排序的最壞時(shí)間復(fù)雜度會(huì)退化到 O(n^2)。這種情況通常發(fā)生在數(shù)組已經(jīng)排序或所有元素相等的情況下。

在當(dāng)前代碼中

使用了三數(shù)取中法來選擇基準(zhǔn)值，這種方法可以在大多數(shù)情況下避免選擇極端值作為基準(zhǔn)，從而減少最壞情況發(fā)生的概率。但是，如果數(shù)組的元素分布非常不均勻，或者存在大量重復(fù)元素，仍然可能遇到性能退化的情況。

此外，代碼中還引入了一個(gè)優(yōu)化：當(dāng)子數(shù)組的大小小于或等于10時(shí)，使用插入排序而不是快速排序。這是因?yàn)閷?duì)于小數(shù)組，插入排序的性能通常比快速排序更好，而且插入排序是穩(wěn)定的。這個(gè)優(yōu)化可以提高算法在處理小數(shù)組時(shí)的效率。

總的來說，這個(gè)改進(jìn)的快速排序算法的平均時(shí)間復(fù)雜度是 O(n log n)，但在最壞情況下仍然是 O(n^2)。然而，由于三數(shù)取中法和插入排序的優(yōu)化，最壞情況的發(fā)生概率被大大降低了。在實(shí)際應(yīng)用中，這種改進(jìn)的快速排序算法通常能夠提供非常高效的排序性能。

前后修改之后速度進(jìn)行對(duì)比

優(yōu)化，和不優(yōu)化之間的區(qū)別

這里計(jì)算的是一千萬個(gè)數(shù)值進(jìn)行排序的毫秒數(shù)值，也就是不到一秒，還是很快的，尤其是修改之后，解決了大量的遞歸問題

注意事項(xiàng)

這里調(diào)用的插入排序是升序，寫的快排也是升序，如果你需要測(cè)試降序，那么你需要把插入排序一起改成降序，不然會(huì)導(dǎo)致排序沖突

快排（前后指針-遞歸解決）

前言

快排解決辦法有很多種，這里我再拿出來一種前后指針版本

雖然這個(gè)版本的時(shí)間復(fù)雜度和霍爾一樣，邏輯也差不多，但是實(shí)際排序過程，確實(shí)會(huì)比霍爾慢一點(diǎn)

快排gif

快排前后指針實(shí)現(xiàn)邏輯：

前后指針實(shí)現(xiàn)邏輯(升序):
單趟排序:
1，我們使用遞歸來進(jìn)行實(shí)現(xiàn)，所以我們先實(shí)現(xiàn)單趟排序
2，定義兩個(gè)下標(biāo)，也就是所謂的指針，初始的時(shí)候，一個(gè)指向最左邊第一個(gè)元素(prev)，一個(gè)指向第二個(gè)元素(cur)，最后定義一個(gè)對(duì)比keyi3，此時(shí)先判斷我們的cur是不是小于keyi。cur小于keyi的話:prev++，交換，之后cur++4，但是我們?nèi)绻妥约航粨Q此時(shí)沒有什么意義，所以這里我們需要做一個(gè)處理
5，繼續(xù)往前走，如果遇見的是:比keyi下標(biāo)大的元素此時(shí)，cur++，直到遇見的是比keyi下標(biāo)小的元素，循環(huán)執(zhí)行.prev++，交換，之后cur++

6，最后cur走到最后一個(gè)元素，我們交換keyi的下標(biāo)元素和prev的下標(biāo)元素

多趟實(shí)現(xiàn):
1，遞歸進(jìn)行分割:【left，keyi-1】keyi【keyi+1，right】
2，停止條件就是當(dāng)left>=right
原因:【left, keyi-1】keyi【keyi+1, right】

快排單趟實(shí)現(xiàn)

這里只是圖解單趟實(shí)現(xiàn)邏輯，因?yàn)槎嗵藢?shí)現(xiàn)的邏輯和霍爾的一樣，也是遞歸，所以不進(jìn)行多次書寫

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

這里的代碼實(shí)現(xiàn)的核心邏輯不一樣，大的框架是一樣的，也就是三數(shù)取中，以及減少遞歸從而使用插入排序這樣的邏輯是一樣的，下面我們來看看這個(gè)新的組裝怪

//快排（前后指針方法）(遞歸實(shí)現(xiàn))
void QuickSort02(int* a, int left, int right)
{//遞歸停止條件if (left >= right)return;//創(chuàng)建兩個(gè)變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當(dāng)快指針到尾的時(shí)候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數(shù)值，所以遇見大的++，小的停止if (a[keyi] > a[cur]){//停止之后，慢指針++,并且進(jìn)行交換,因?yàn)橹虚g才是大的數(shù)值，cur遇見大數(shù)值++。遇見小數(shù)值才停下來prev++;Swap(&a[prev], &a[cur]);//同理快指針也進(jìn)行++，往后移動(dòng)cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;//多趟遞歸實(shí)現(xiàn)//[left,keyi-1] keyi [keyi+1,right]   這里傳遞的是區(qū)間//  1     0      1     2      1       當(dāng)只剩一個(gè)數(shù)值的時(shí)候，也就是這個(gè)區(qū)間的時(shí)候，遞歸停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi + 1, right);
}

總結(jié)：

1. 算法基礎(chǔ)：快速排序是一種分而治之的排序算法，它通過遞歸地將數(shù)組分為較小的子數(shù)組，然后對(duì)這些子數(shù)組進(jìn)行排序。

2. 分區(qū)策略：使用前后指針（prev和cur）進(jìn)行分區(qū)，而不是傳統(tǒng)的左右指針。這種方法在某些情況下可以減少元素交換的次數(shù)。

3. 基準(zhǔn)值選擇：基準(zhǔn)值（keyi）是數(shù)組的第一個(gè)元素，即left索引對(duì)應(yīng)的元素。

4. 指針移動(dòng)規(guī)則：

   • prev作為慢指針，用于跟蹤比基準(zhǔn)值小的元素的邊界。
   • cur作為快指針，從left + 1開始遍歷數(shù)組。

5. 元素交換：當(dāng)快指針指向的元素大于基準(zhǔn)值時(shí)，不進(jìn)行交換，快指針繼續(xù)移動(dòng)；當(dāng)快指針指向的元素小于或等于基準(zhǔn)值時(shí)，與慢指針?biāo)冈亟粨Q，然后慢指針和快指針都向前移動(dòng)。

6. 遞歸排序：在基準(zhǔn)值確定之后，遞歸地對(duì)基準(zhǔn)值左邊和右邊的子數(shù)組進(jìn)行排序。

7. 時(shí)間復(fù)雜度：平均情況下，快速排序的時(shí)間復(fù)雜度為O(n log n)。最壞情況下，如果每次分區(qū)都極不平衡，時(shí)間復(fù)雜度會(huì)退化到O(n^2)。

8. 空間復(fù)雜度：由于遞歸性質(zhì)，快速排序的空間復(fù)雜度為O(log n)。

9. 算法優(yōu)化：通過前后指針方法，可以在某些情況下提高快速排序的性能，特別是當(dāng)基準(zhǔn)值接近數(shù)組中間值時(shí)。

10. 適用場(chǎng)景：快速排序適用于大多數(shù)需要排序的場(chǎng)景，特別是在大數(shù)據(jù)集上，它通常能夠提供非常高效的排序性能。

優(yōu)化

這里我們可以看到，cur無論是if還是else里面都需要++，所以我們直接放到外面

其次我們?yōu)榱诵?#xff0c;不和自己交換，我們不和自己交換，進(jìn)行一個(gè)判斷條件

快慢指針代碼優(yōu)化（完整）

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//快排（前后指針方法）(遞歸實(shí)現(xiàn))
void QuickSort02(int* a, int left, int right)
{//遞歸停止條件if (left >= right)return;if (right - left + 1 >= 10){InsertionSort(a + left, right - left + 1);}else{//三數(shù)取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實(shí)現(xiàn)//創(chuàng)建兩個(gè)變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當(dāng)快指針到尾的時(shí)候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數(shù)值，所以遇見大的++，小的停止if (a[keyi] > a[cur] && prev++ != cur){//停止之后，慢指針++,并且進(jìn)行交換,因?yàn)橹虚g才是大的數(shù)值，cur遇見大數(shù)值++。遇見小數(shù)值才停下來Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;//多趟遞歸實(shí)現(xiàn)//[left,keyi-1] keyi [keyi+1,right]   這里傳遞的是區(qū)間//  1     0      1     2      1       當(dāng)只剩一個(gè)數(shù)值的時(shí)候，也就是這個(gè)區(qū)間的時(shí)候，遞歸停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi + 1, right);}
}

總結(jié)：

1. 基本遞歸結(jié)構(gòu)：算法使用遞歸調(diào)用來處理子數(shù)組，這是快速排序算法的核心結(jié)構(gòu)。

2. 小數(shù)組優(yōu)化：當(dāng)子數(shù)組的大小小于或等于10時(shí)，算法使用插入排序而不是快速排序，因?yàn)椴迦肱判蛟谛∫?guī)模數(shù)據(jù)上更高效。

3. 三數(shù)取中法：為了更均勻地分割數(shù)組，算法使用三數(shù)取中法選擇基準(zhǔn)值，這有助于減少最壞情況發(fā)生的概率。

4. 前后指針方法：算法使用兩個(gè)指針（prev和cur），其中prev作為慢指針，cur作為快指針，通過這種方式進(jìn)行一次遍歷完成分區(qū)。

5. 分區(qū)操作：快指針從left + 1開始遍歷，如果當(dāng)前元素小于基準(zhǔn)值，則與慢指針?biāo)傅脑亟粨Q，然后慢指針向前移動(dòng)。

6. 遞歸排序子數(shù)組：基準(zhǔn)值確定后，算法遞歸地對(duì)基準(zhǔn)值左邊和右邊的子數(shù)組進(jìn)行排序。

7. 時(shí)間復(fù)雜度：平均情況下，算法的時(shí)間復(fù)雜度為O(n log n)，最壞情況下為O(n^2)。但由于采用了小數(shù)組優(yōu)化和三數(shù)取中法，最壞情況的發(fā)生概率降低。

8. 空間復(fù)雜度：算法的空間復(fù)雜度為O(log n)，這主要由于遞歸調(diào)用導(dǎo)致的?？臻g使用。

9. 適用場(chǎng)景：這種改進(jìn)的快速排序算法適用于大多數(shù)需要排序的場(chǎng)景，尤其是在大數(shù)據(jù)集上，它能夠提供非常高效的排序性能，同時(shí)在小數(shù)據(jù)集上也表現(xiàn)出較好的效率。

10. 算法穩(wěn)定性：由于使用了插入排序?qū)π∫?guī)模子數(shù)組進(jìn)行排序，算法在處理小規(guī)模數(shù)據(jù)時(shí)具有穩(wěn)定性。

11. 注意：在實(shí)際測(cè)試·里面，前后指針比霍爾排序慢一點(diǎn)

通過這種混合排序策略，算法在保持快速排序優(yōu)點(diǎn)的同時(shí)，也提高了在特定情況下的排序效率，使其成為一種更加健壯的排序方法。

注意事項(xiàng)

這里調(diào)用的插入排序是升序，寫的快排也是升序，如果你需要測(cè)試降序，那么你需要把插入排序一起改成降序，不然會(huì)導(dǎo)致排序沖突

快排（霍爾版本-非遞歸解決）

前言

快拍不僅需要學(xué)習(xí)遞歸，還需要學(xué)東西非遞歸，這樣更有助于我們理解快拍

首先我們需要知道，非遞歸的學(xué)習(xí)需要使用棧，所以如果我們的棧的學(xué)習(xí)是不完善的，建議學(xué)習(xí)一下棧

非遞歸gif

這里其實(shí)單詞循環(huán)是誰其實(shí)不重要，可以是前后指針，也可以是霍爾方式，這里我們拿出來霍爾的gif來觀看

實(shí)現(xiàn)圖解

非遞歸實(shí)現(xiàn)主要是依賴棧來進(jìn)行實(shí)現(xiàn)，依賴棧的特點(diǎn)，先進(jìn)后出，后進(jìn)前出

1，首先我們需要寫一個(gè)棧的庫進(jìn)行調(diào)用

2，入?yún)^(qū)間，調(diào)用單次排序的實(shí)現(xiàn)思路

3，入?yún)^(qū)間的時(shí)候，我們需要把握入棧和出棧的關(guān)鍵

代碼實(shí)現(xiàn)（前后指針）

首先我們調(diào)用棧

頭文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{STDataType* _a; // 首元素的地址int _top;		// 棧頂，初始化為0，也就是等同于size，初始化為-1，等同于下標(biāo)int _capacity;  // 容量 
}Stack;
// 初始化棧 
void StackInit(Stack* ps);
// 銷毀棧 
void StackDestroy(Stack* ps);
// 入棧 
void StackPush(Stack* ps, STDataType data);
// 出棧 
void StackPop(Stack* ps);
// 獲取棧頂元素 
STDataType StackTop(Stack* ps);
// 獲取棧尾元素 
STDataType Stackhop(Stack* ps);
// 獲取棧中有效元素個(gè)數(shù) 
int StackSize(Stack* ps);
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
int StackEmpty(Stack* ps);

實(shí)現(xiàn)文件

#include"Stack.h"
// 初始化棧 
void StackInit(Stack* ps)
{ps->_a = NULL;ps->_capacity = ps->_top = 0;
}
// 銷毀棧 
void StackDestroy(Stack* ps)
{assert(ps && ps->_top);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;
}// 入棧 
void StackPush(Stack* ps, STDataType data)
{//判斷需不需要擴(kuò)容,相等的時(shí)候需要擴(kuò)容if (ps->_capacity == ps->_top){//判斷空間是不是0，因?yàn)闉?的時(shí)候，再多的數(shù)值*2,也是0int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("StackPush:tmp:err:");return;}ps->_capacity = newcapacity;ps->_a = tmp;}ps->_a[ps->_top] = data;ps->_top++;
}// 出棧 
void StackPop(Stack* ps)
{assert(ps);ps->_top--;
}
// 獲取棧頂元素 
STDataType StackTop(Stack* ps)
{//這里必須大于0 因?yàn)槲覀冞@里等同size，也就是個(gè)數(shù)，等于0都不行assert(ps);return ps->_a[ps->_top - 1];
}
// 獲取棧尾元素 
STDataType Stackhop(Stack* ps)
{assert(ps && ps->_top > 0);return ps->_a[0];
}
// 獲取棧中有效元素個(gè)數(shù) 
int StackSize(Stack* ps)
{//獲取有效元素的時(shí)候，里面可以沒有元素assert(ps);return ps->_top;
}
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
int StackEmpty(Stack* ps)
{//這里的判斷是不是空，也就是里面是不是有數(shù)值，這里等于是一個(gè)判斷，沒有的話返回ture，有的話返回falseassert(ps);return ps->_top == 0;
}

其次調(diào)用前后指針來實(shí)現(xiàn)

//快排（前后指針方法）(單趟)
int one_QuickSort02(int* a, int left, int right)
{//三數(shù)取中//int mid = GetMid(a, left, right);//Swap(&a[mid], &a[left]);//單趟實(shí)現(xiàn)//創(chuàng)建兩個(gè)變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當(dāng)快指針到尾的時(shí)候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數(shù)值，所以遇見大的++，小的停止if (a[keyi] > a[cur] && prev++ != cur){//停止之后，慢指針++,并且進(jìn)行交換,因?yàn)橹虚g才是大的數(shù)值，cur遇見大數(shù)值++。遇見小數(shù)值才停下來Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;                                                                                                                                                                   //快排 非遞歸實(shí)現(xiàn)
void QuickSort003(int* a, int left, int right)
{//非遞歸實(shí)現(xiàn)主要是用棧來模擬實(shí)現(xiàn)，在c++里面我們可以直接調(diào)用棧，但是在C語言里面我們只能寫出來?xiàng)Ｔ龠M(jìn)行調(diào)用//思路（霍爾方式）//1單趟的思路還是一樣的，如果是升序的情況下，依舊是先從右邊出發(fā)（找小），后從左邊出發(fā)（找大）//2,循環(huán)遞歸過程我們改為利用進(jìn)棧出棧來實(shí)現(xiàn)。首先我們需要明確這里傳遞的是區(qū)間，也就是利用棧實(shí)現(xiàn)的時(shí)候，我們傳遞的是數(shù)組和區(qū)間，利用區(qū)間進(jìn)行計(jì)算。這里的關(guān)鍵在于傳遞區(qū)間的時(shí)候，我們需要詳細(xì)知曉棧的特點(diǎn)，先進(jìn)后出，后進(jìn)后出，。所以在傳遞區(qū)間的時(shí)候，如果多趟循環(huán)，一分為二的時(shí)候，我們需要先傳遞右側(cè)的區(qū)間，再傳遞左側(cè)區(qū)間，因?yàn)槲覀冃枰扔?jì)算左側(cè)。同理進(jìn)去之后，我們需要繼續(xù)入棧，需要先-入計(jì)算左側(cè)的區(qū)間的右側(cè)區(qū)間，后入左側(cè)區(qū)間。這樣就會(huì)先計(jì)算左側(cè)區(qū)間。棧的特性，先進(jìn)后出，后進(jìn)先出// // 所以這里我們把霍爾排序單趟實(shí)現(xiàn)來單獨(dú)拿出來，這樣的話我們接受的返回值是中間值//[left,keyi-1] keyi [keyi+1,right]//這里需要用非遞歸來解決Stack ps;StackInit(&ps);StackPush(&ps, right);StackPush(&ps, left);while (!StackEmpty(&ps)){int begin = StackTop(&ps);StackPop(&ps);int end = StackTop(&ps);StackPop(&ps);//假設(shè)入棧區(qū)間此時(shí)來到-> 0-2int mini = one_QuickSort02(a, begin, end);//經(jīng)過計(jì)算之后，此時(shí)中間值是，keyi=1//0 1 2  三個(gè)區(qū)間三個(gè)數(shù)值，此時(shí)進(jìn)行入棧判斷//[begin,keyi-1]keyi[keyi+1,end]//[  0  ,  0   ] 1  [  2   , 2 ]//所以不繼續(xù)入棧if (mini + 1 < end){//右邊先入棧，后計(jì)算StackPush(&ps, end);StackPush(&ps, mini + 1);}if (mini - 1 > begin){//左邊區(qū)間后入棧，先計(jì)算StackPush(&ps, mini - 1);StackPush(&ps, begin);}}StackDestroy(&ps);
}

解釋：

one_QuickSort02?函數(shù)

這個(gè)函數(shù)是快速排序算法中的單趟排序?qū)崿F(xiàn)。它使用前后指針法來實(shí)現(xiàn)，具體步驟如下：

1. 初始化指針：prev?初始化為?left，cur?初始化為?prev + 1，keyi?也初始化為?left。
2. 循環(huán)：當(dāng)?cur?小于等于?right?時(shí)，執(zhí)行循環(huán)體內(nèi)的操作。
3. 比較和交換：如果當(dāng)前?cur?指向的元素小于?keyi?指向的元素，并且?prev?指針不等于?cur，說明找到了一個(gè)比基準(zhǔn)值小的元素，需要交換。將?a[prev]?和?a[cur]?交換，并將?prev?指針向前移動(dòng)一位。
4. 移動(dòng)快指針：無論是否發(fā)生交換，cur?指針都向前移動(dòng)一位。
5. 交換基準(zhǔn)值：循環(huán)結(jié)束后，將?keyi?指向的元素與?prev?指向的元素交換，此時(shí)?prev?指向的是比基準(zhǔn)值小的元素的最后一個(gè)位置。
6. 返回值：函數(shù)返回?prev?的值，這個(gè)值是下一次分區(qū)的起始位置。

QuickSort003?函數(shù)

這個(gè)函數(shù)是快速排序的非遞歸實(shí)現(xiàn)，使用棧來模擬遞歸過程。具體步驟如下：

1. 初始化棧：創(chuàng)建并初始化一個(gè)棧?ps。
2. 入棧：將?left?和?right?作為初始區(qū)間入棧。
3. 循環(huán)：只要棧不為空，就執(zhí)行循環(huán)。
4. 單趟排序：每次從棧中取出兩個(gè)值作為區(qū)間的左右邊界，調(diào)用?one_QuickSort02?函數(shù)進(jìn)行單趟排序，得到中間值?mini。
5. 判斷區(qū)間：根據(jù)?mini?的位置，判斷是否需要繼續(xù)對(duì)左右區(qū)間進(jìn)行排序。
   • 如果?mini + 1 < end，則說明右側(cè)還有元素需要排序，將?end?和?mini + 1?入棧。
   • 如果?mini - 1 > begin，則說明左側(cè)還有元素需要排序，將?begin?和?mini - 1?入棧。
6. 出棧：每次循環(huán)結(jié)束，都會(huì)從棧中彈出兩個(gè)值，直到棧為空。
7. 銷毀棧：循環(huán)結(jié)束后，銷毀棧。

對(duì)于棧和隊(duì)列不是很明白的，推薦看一下棧和隊(duì)列篇章

數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列(速通版本)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138715165

代碼實(shí)現(xiàn)（霍爾排序）

這里其實(shí)不管是前后指針，還是霍爾排序，其實(shí)都是一樣的，因?yàn)楸举|(zhì)上都是讓數(shù)值到應(yīng)該到的位置，所以本質(zhì)上是一樣的，這里我再調(diào)用一個(gè)霍爾的方式是因?yàn)橐环矫婧颓昂笾羔樀恼{(diào)用形成對(duì)比，一方面有不同的注釋

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//霍爾方法(單趟實(shí)現(xiàn))
int one_QuickSort01(int* a, int left, int right)
{//三數(shù)取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實(shí)現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動(dòng),是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動(dòng)，是的話不移動(dòng)，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}
//霍爾方法再次調(diào)用
void QuickSort03(int* a, int left, int right)
{Stack ps;StackInit(&ps);StackPush(&ps, right);StackPush(&ps, left);while (!StackEmpty(&ps)){//取出左區(qū)間int begin = StackTop(&ps);StackPop(&ps);//取出右邊區(qū)間int end = StackTop(&ps);StackPop(&ps);int mini = one_QuickSort01(a, begin, end);//計(jì)算區(qū)間//假設(shè)傳遞的區(qū)間是2-4 --->>> 傳遞過來的數(shù)值也就是下標(biāo)是（1）4-2=2/2=1 --->>>此時(shí)mini=2,也就是此時(shí)我們返回的數(shù)值要么是第一個(gè)數(shù)值，要么的第二個(gè)數(shù)值的下標(biāo)，不管是哪個(gè)，此時(shí)都會(huì)變成一個(gè)數(shù)值//此時(shí)我們繼續(xù)入棧，入棧的是mini+1 也就是3-4，繼續(xù)傳遞區(qū)間，此時(shí)傳遞回來的mini還是3，但是此時(shí)3+4==4了 所以不繼續(xù)入棧，因?yàn)閿?shù)值只有一個(gè)，不是區(qū)間了//右區(qū)間入棧，后出if (mini + 1 < end){//入右邊，之后左邊，這樣取的時(shí)候棧頂先取左邊，之后右邊StackPush(&ps, end);StackPush(&ps, mini + 1);}//左區(qū)間入棧，先出if (mini - 1 > begin){StackPush(&ps, mini - 1);StackPush(&ps, begin);}}StackDestroy(&ps);
}

解釋：

one_QuickSort01?函數(shù)

這個(gè)函數(shù)是霍爾快速排序算法的單趟實(shí)現(xiàn)，具體步驟如下：

1. 三數(shù)取中：使用?GetMid?函數(shù)找到數(shù)組?a?中間位置的元素，并將其與數(shù)組第一個(gè)元素交換（left?索引位置的元素）。
2. 初始化指針：begin?初始化為?left，end?初始化為?right，keyi?初始化為?begin。
3. 循環(huán)：使用?while?循環(huán)，只要?begin?小于?end，就繼續(xù)執(zhí)行循環(huán)。
4. 右邊找小：從?end?向?begin?掃描，找到第一個(gè)小于基準(zhǔn)值?a[keyi]?的元素。如果找到，end?指針向前移動(dòng)，否則跳出循環(huán)。
5. 左邊找大：從?begin?向?end?掃描，找到第一個(gè)大于基準(zhǔn)值?a[keyi]?的元素。如果找到，begin?指針向后移動(dòng)，否則跳出循環(huán)。
6. 交換元素：將找到的兩個(gè)元素?a[begin]?和?a[end]?交換位置。
7. 基準(zhǔn)值交換：循環(huán)結(jié)束后，將?keyi?指向的元素與?begin?指向的元素交換，此時(shí)?begin?指向的是基準(zhǔn)值的正確位置。
8. 返回值：函數(shù)返回?begin?的值，這個(gè)值是下一次分區(qū)的起始位置。

QuickSort03?函數(shù)

這個(gè)函數(shù)是快速排序的非遞歸實(shí)現(xiàn)，使用棧來模擬遞歸過程：

1. 初始化棧：創(chuàng)建并初始化一個(gè)棧?ps。
2. 入棧：將初始區(qū)間的左右邊界?left?和?right?入棧。
3. 循環(huán)：只要棧不為空，就繼續(xù)執(zhí)行循環(huán)。
4. 單趟排序：每次從棧中取出兩個(gè)值作為區(qū)間的左右邊界，調(diào)用?one_QuickSort01?函數(shù)進(jìn)行單趟排序，得到中間值?mini。
5. 計(jì)算新區(qū)間：根據(jù)?mini?的位置，計(jì)算新的左右區(qū)間。
   • 如果?mini + 1 < end，則說明右側(cè)還有元素需要排序，將?end?和?mini + 1?入棧。
   • 如果?mini - 1 > begin，則說明左側(cè)還有元素需要排序，將?begin?和?mini - 1?入棧。
6. 棧的特性：由于棧是后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，所以先入棧的是右側(cè)區(qū)間，后入棧的是左側(cè)區(qū)間，這樣在出棧時(shí)，會(huì)先處理左側(cè)區(qū)間，再處理右側(cè)區(qū)間。
7. 銷毀棧：循環(huán)結(jié)束后，銷毀棧。

這種非遞歸實(shí)現(xiàn)的快速排序算法利用了棧的特性來避免遞歸調(diào)用，從而減少了函數(shù)調(diào)用的開銷，并且在處理大數(shù)據(jù)集時(shí)，可以避免遞歸深度過大導(dǎo)致的棧溢出問題。

歸并排序?（遞歸實(shí)現(xiàn)）

前言

歸并排序是一種邏輯很簡(jiǎn)單，但是實(shí)現(xiàn)有點(diǎn)難度的排序，尤其是非遞歸，對(duì)于區(qū)間的把握更是需要一點(diǎn)邏輯的推導(dǎo)，但是沒有關(guān)系，輕松拿捏

歸并排序gif

歸并排序單趟實(shí)現(xiàn)

1，創(chuàng)建tmp數(shù)組，

2，遞歸到最小值進(jìn)行排序，同時(shí)拷貝到題目破數(shù)組里面

3，這里的關(guān)鍵邏輯實(shí)現(xiàn)是，遞歸回來的時(shí)候進(jìn)行排序

4，最后我們把數(shù)值重新拷貝回去原數(shù)組

注意：這里的取值我們直接取中間值進(jìn)行遞歸，一分為二

代碼實(shí)現(xiàn)注意事項(xiàng)

關(guān)于創(chuàng)建tmp數(shù)組，我們需要?jiǎng)?chuàng)建的數(shù)組應(yīng)該是等大的，要么就進(jìn)行初始化。

• 因?yàn)槲覀兪莔alloc出來的空間，
• 為什么malloc出來的空間必須是等大的，因?yàn)檫@里我們用的是Visual Studio 2022的編譯器，這個(gè)編譯器里面是不支持可變長數(shù)組的。所以我們需要用malloc，或者realloc來實(shí)現(xiàn)創(chuàng)建空間，也就是動(dòng)態(tài)內(nèi)存的分配
• malloc創(chuàng)建空間的時(shí)候，空間里面是有隨機(jī)值的
• realloc創(chuàng)建的空間里面的數(shù)值是0
• 所以一旦我們進(jìn)行排序的時(shí)候，如果我們不進(jìn)行覆蓋的話，這里面的數(shù)值也會(huì)參與排序，從而導(dǎo)致數(shù)值出現(xiàn)偏差

這里對(duì)于這一點(diǎn)不清楚的可以看看之前寫的文章，因?yàn)楫?dāng)時(shí)寫這個(gè)文章的時(shí)候，剛接觸編程，所以講述的主要是以語法和一些簡(jiǎn)單的性質(zhì)特點(diǎn)，希望可以起到幫助

• 動(dòng)態(tài)內(nèi)存函數(shù)的使用和綜合實(shí)踐-malloc，free，realloc，calloc_內(nèi)存申請(qǐng)函數(shù)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/137075045

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

//歸并排序（遞歸實(shí)現(xiàn)）子函數(shù)(實(shí)現(xiàn)函數(shù))
void _MergeSort01(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mini = (begin + end) / 2;//注意，這里關(guān)鍵在于，區(qū)間的傳遞，//不應(yīng)該傳遞【left,mini-1】【mini,right】//  應(yīng)該傳遞【left,mini】【mini+1,right】//遞歸左右區(qū)間, 遞歸到最小個(gè)數(shù)進(jìn)行對(duì)比_MergeSort01(a, tmp, begin, mini);_MergeSort01(a, tmp, mini + 1, end);int begin1 = begin, end1 = mini;int begin2 = mini + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//數(shù)據(jù)從tmp拷貝回去數(shù)組a里面memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//歸并排序（遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort01(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}_MergeSort01(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

解釋：

1. _MergeSort01 函數(shù)：這是歸并排序的遞歸子函數(shù)，它接收三個(gè)參數(shù)：數(shù)組 a，臨時(shí)數(shù)組 tmp，以及要排序的數(shù)組區(qū)間 [begin, end]。

   • 如果?begin?大于或等于?end，則表示區(qū)間內(nèi)沒有元素或只有一個(gè)元素，不需要排序，直接返回。
   • 計(jì)算區(qū)間的中點(diǎn)?mini，將數(shù)組分為兩部分：[begin, mini]?和?[mini + 1, end]。
   • 對(duì)這兩部分分別遞歸調(diào)用?_MergeSort01?函數(shù)進(jìn)行排序，直到每個(gè)子區(qū)間只有一個(gè)元素。

2. 合并過程：

   • 初始化兩個(gè)指針?begin1?和?end1?指向第一個(gè)子區(qū)間的開始和結(jié)束位置，begin2?和?end2?指向第二個(gè)子區(qū)間的開始和結(jié)束位置。
   • 使用一個(gè)索引?i?指向?tmp?數(shù)組的當(dāng)前位置，用于存放合并后的有序元素。
   • 使用兩個(gè)?while?循環(huán)來比較兩個(gè)子區(qū)間的元素，將較小的元素復(fù)制到?tmp?數(shù)組中，并移動(dòng)對(duì)應(yīng)的指針。
   • 如果第一個(gè)子區(qū)間的所有元素已經(jīng)被復(fù)制到?tmp?中，但第二個(gè)子區(qū)間還有剩余元素，將這些剩余元素復(fù)制到?tmp?數(shù)組的剩余位置。
   • 同理，如果第二個(gè)子區(qū)間的所有元素已經(jīng)被復(fù)制，將第一個(gè)子區(qū)間的剩余元素復(fù)制到?tmp。

3. 拷貝回原數(shù)組：

   • 使用?memcpy?函數(shù)將?tmp?數(shù)組中從索引?begin?開始的元素復(fù)制回原數(shù)組?a。這里計(jì)算了需要復(fù)制的元素?cái)?shù)量為?end - begin + 1，乘以?sizeof(int)?來確定字節(jié)數(shù)。

4. MergeSort01 函數(shù)：這是歸并排序的初始化函數(shù)，接收數(shù)組 a 和數(shù)組的長度 n。

   • 首先，使用?malloc?分配一個(gè)臨時(shí)數(shù)組?tmp，大小為?n?個(gè)?int。
   • 如果內(nèi)存分配失敗，使用?perror?打印錯(cuò)誤信息，并調(diào)用?exit(1)?退出程序。
   • 調(diào)用?_MergeSort01?函數(shù)，傳入數(shù)組?a、臨時(shí)數(shù)組?tmp?和整個(gè)數(shù)組的區(qū)間?[0, n - 1]?進(jìn)行排序。
   • 排序完成后，使用?free?釋放?tmp?所占用的內(nèi)存，并設(shè)置?tmp?為?NULL。

歸并排序的時(shí)間復(fù)雜度為 O(n log n)，在大多數(shù)情況下表現(xiàn)良好，尤其是當(dāng)數(shù)據(jù)量大且需要穩(wěn)定排序時(shí)。不過，由于它需要額外的內(nèi)存空間（如這里的 tmp 數(shù)組），在內(nèi)存受限的情況下可能不是最佳選擇。

遞歸排序（非遞歸解決）

前言

這里遞歸排序的非遞歸方式還是比較有難度的，所以需要多次觀看兩遍，我也會(huì)多次詳細(xì)的講解，促進(jìn)知識(shí)的理解

非遞歸實(shí)現(xiàn)gif

非遞歸實(shí)現(xiàn)單趟實(shí)現(xiàn)

這里的關(guān)鍵的在于對(duì)于區(qū)間的理解

尤其是

?? ??? ??? ?//但是此時(shí)可能產(chǎn)生越界行為,我們可以打印出來看一下
?? ??? ??? ?//產(chǎn)生越界的
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? ? ? ? ? ? ? ? end2->[,][,15]
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? ? ? ? begin2, end2->[,][12,15]
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? end1, begin2, end2->[,11][12,15]
?? ??? ??? ?//解決
?? ??? ??? ?//begin2, end2區(qū)間越界的，我們直接下一次進(jìn)行遞歸就可以
?? ??? ??? ?//end2，我們重新設(shè)定新的end2的區(qū)間

所以我們需要對(duì)這個(gè)區(qū)間進(jìn)行解決

代碼的逐步實(shí)現(xiàn)

這里代碼的實(shí)現(xiàn)，因?yàn)榉沁f歸實(shí)現(xiàn)是有難度的，所以這里我不會(huì)直接給出答案，而是逐步的寫出步驟，促進(jìn)理解

1，創(chuàng)建拷貝空間tmp，設(shè)定gap，一組假設(shè)初始1個(gè)數(shù)值，當(dāng)然初始的時(shí)候，實(shí)際也是一個(gè)數(shù)值

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;
}

2，區(qū)間的設(shè)定

這里依舊是兩個(gè)區(qū)間，我們根據(jù)這個(gè)區(qū)間設(shè)定的數(shù)值

這里是很關(guān)鍵的一點(diǎn)

?? ?int begin1 = 0, end1 = 0 + gap - 1;
?? ?int begin2 = 0 + gap, end2 = 0 + 2 * gap - 1;

//假設(shè)此時(shí)就兩個(gè)數(shù)值，一組是一個(gè)數(shù)值，也就是這兩個(gè)數(shù)值進(jìn)行最小對(duì)比

//begin1左區(qū)間的初始位置，肯定是0

//end1左區(qū)間的結(jié)束位置。

• 也就是第一個(gè)區(qū)間的結(jié)束位置，也就是一組，
• -1是因?yàn)橐唤M是實(shí)際的個(gè)數(shù)
• +0，這里因?yàn)榧拥氖堑谝粋€(gè)區(qū)間起始位置
• 因?yàn)槲覀円部赡苁?-4區(qū)間的，不可能只是這一個(gè)區(qū)間

//begin2第二個(gè)區(qū)間的起始位置，這里還是比較好理解的，只要理解了end1

//end2第二個(gè)區(qū)間的結(jié)束位置，這里同理，

• 我們有可能是2-4區(qū)間的，不只是0-1或者0-2區(qū)間的。而且隨著第一次排序的結(jié)束，第二次排序就變成兩個(gè)合并了，繼續(xù)和另外的對(duì)比，所以是變化的
• 0也就是初始位置
• 2*gap，因?yàn)檫@里是需要加上中間兩組，
• 最后-1，因?yàn)間ap是個(gè)數(shù)，不是下標(biāo)

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;int begin1 = 0, end1 = 0 + gap - 1;int begin2 = 0 + gap, end2 = 0 + 2 * gap - 1;
}

3，排序的實(shí)現(xiàn)

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;while (gap < n){//遞歸到最小值,假設(shè)一組是一個(gè),也就是此時(shí)是最小值進(jìn)行比較并且入數(shù)組，關(guān)鍵是找出區(qū)間//這里一次跳過兩組for (int i = 0; i < n - 1; i = i + gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}gap *= 2;}
}

4，區(qū)間的拷貝

這里區(qū)間的拷貝我們需要注意的是我們拷貝的是區(qū)間，并且我們需要一邊拷貝一邊拷貝回去，為什么需要一邊排序一邊拷貝回去，在接下來的越界行為里面我們會(huì)進(jìn)行講解

最后需要關(guān)注的點(diǎn)是，關(guān)于拷貝空間的大小，一定是end2-begin1，因?yàn)檫@兩個(gè)區(qū)間是排序成功然后進(jìn)入到tmp里面

所以我們需要從tmp拷貝回去，不能弄錯(cuò)了

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;while (gap < n){//遞歸到最小值,假設(shè)一組是一個(gè),也就是此時(shí)是最小值進(jìn)行比較并且入數(shù)組，關(guān)鍵是找出區(qū)間//這里一次跳過兩組for (int i = 0; i < n - 1; i = i + gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷貝回a數(shù)組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}
}

5，解決越界行為

這里我們可以很清楚的看到哪些位置會(huì)產(chǎn)生越界行為

這里我們處理一下之后，我們發(fā)現(xiàn)就解決了

?? ??? ??? ?//產(chǎn)生越界的區(qū)間有
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? ? ? ? ? ? ? ? end2->[,][,15]
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? ? ? ? begin2, end2->[,][12,15]
?? ??? ??? ?//begin1, end1, begin2, end2 -> ? ? ? ? end1, begin2, end2->[,11][12,15]
?? ??? ??? ?//解決
?? ??? ??? ?//begin2, end2區(qū)間越界的，我們直接下一次進(jìn)行遞歸就可以
?? ??? ??? ?//end2，我們重新設(shè)定新的end2的區(qū)間

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;while (gap < n){//遞歸到最小值,假設(shè)一組是一個(gè),也就是此時(shí)是最小值進(jìn)行比較并且入數(shù)組，關(guān)鍵是找出區(qū)間//這里一次跳過兩組for (int i = 0; i < n - 1; i = i + gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//但是此時(shí)可能產(chǎn)生越界行為,我們可以打印出來看一下//產(chǎn)生越界的//begin1, end1, begin2, end2 ->                       end2->[,][,15]//begin1, end1, begin2, end2 ->               begin2, end2->[,][12,15]//begin1, end1, begin2, end2 ->         end1, begin2, end2->[,11][12,15]//解決//begin2, end2區(qū)間越界的，我們直接下一次進(jìn)行遞歸就可以//end2，我們重新設(shè)定新的end2的區(qū)間printf("[begin1=%d,end1=%d][begin2=%d,end2=%d]\n", begin1, end1, begin2, end2);if (begin2 > n){break;}if (end2 > n){//記得這里需要是n-1不能是n，因?yàn)閑nd2是下標(biāo)end2 = n-1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷貝回a數(shù)組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}
}

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

時(shí)間復(fù)雜度分析如下：

1. 分解階段：歸并排序首先將原始數(shù)組分解成多個(gè)子數(shù)組，每個(gè)子數(shù)組的大小為1。這個(gè)過程是線性的，時(shí)間復(fù)雜度為 O(n)，其中 n 是原始數(shù)組的大小。

2. 合并階段：在合并階段，算法將這些有序的子數(shù)組逐步合并成更大的有序數(shù)組。每次合并操作都需要將兩個(gè)有序數(shù)組合并成一個(gè)更大的有序數(shù)組，這個(gè)過程的時(shí)間復(fù)雜度是 O(n)。

3. 重復(fù)合并：歸并排序的合并階段會(huì)重復(fù)進(jìn)行，直到所有的元素都被合并成一個(gè)有序數(shù)組。合并的次數(shù)可以看作是對(duì)數(shù)級(jí)的，具體來說，是 log2(n) 次。

綜合以上兩點(diǎn)，歸并排序的總時(shí)間復(fù)雜度主要由合并階段決定，因?yàn)榉纸怆A段是線性的，而合并階段雖然每次都是線性的，但由于重復(fù)了對(duì)數(shù)級(jí)次數(shù)，所以總的時(shí)間復(fù)雜度是：

𝑂(𝑛)+𝑂(𝑛log?𝑛)

由于在大 O 符號(hào)中，我們只關(guān)注最高次項(xiàng)和系數(shù)，所以歸并排序的時(shí)間復(fù)雜度通常被簡(jiǎn)化為：𝑂(𝑛log?𝑛)

這意味著歸并排序的時(shí)間效率與數(shù)組的大小成對(duì)數(shù)關(guān)系，是相當(dāng)高效的排序算法。此外，歸并排序是一種穩(wěn)定的排序算法，它保持了相等元素的原始順序。然而，它需要與原始數(shù)組同樣大小的額外空間來存儲(chǔ)臨時(shí)數(shù)組，這可能會(huì)在空間受限的情況下成為一個(gè)問題。

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

//歸并排序（非遞歸實(shí)現(xiàn)）（創(chuàng)建tmp函數(shù)）
void MergeSort02(int* a, int n)
{//這里n傳遞過來的是個(gè)數(shù)int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設(shè)初始化起始是一組int gap = 1;while (gap < n){//遞歸到最小值,假設(shè)一組是一個(gè),也就是此時(shí)是最小值進(jìn)行比較并且入數(shù)組，關(guān)鍵是找出區(qū)間//這里一次跳過兩組for (int i = 0; i < n - 1; i = i + gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//但是此時(shí)可能產(chǎn)生越界行為,我們可以打印出來看一下//產(chǎn)生越界的//begin1, end1, begin2, end2 ->                       end2->[,][,15]//begin1, end1, begin2, end2 ->               begin2, end2->[,][12,15]//begin1, end1, begin2, end2 ->         end1, begin2, end2->[,11][12,15]//解決//begin2, end2區(qū)間越界的，我們直接下一次進(jìn)行遞歸就可以//end2，我們重新設(shè)定新的end2的區(qū)間printf("[begin1=%d,end1=%d][begin2=%d,end2=%d]\n", begin1, end1, begin2, end2);if (begin2 > n){break;}if (end2 > n){//記得這里需要是n-1不能是n，因?yàn)閑nd2是下標(biāo)end2 = n-1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷貝回a數(shù)組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}
}

解釋：

1. 內(nèi)存分配：首先，函數(shù)使用 malloc 分配一個(gè)與原數(shù)組 a 同樣大小的臨時(shí)數(shù)組 tmp。如果內(nèi)存分配失敗，使用 perror 打印錯(cuò)誤信息，并調(diào)用 exit 退出程序。

2. 初始化間隔：gap 變量初始化為 1，表示每個(gè)元素自身作為一個(gè)有序的子數(shù)組。

3. 外層循環(huán)：使用 while 循環(huán)來逐步增加 gap 的值，每次迭代將 gap 乘以 2。這個(gè)循環(huán)繼續(xù)進(jìn)行，直到 gap 大于或等于數(shù)組的長度 n。

4. 內(nèi)層循環(huán)：對(duì)于每個(gè) gap 值，使用 for 循環(huán)遍歷數(shù)組，計(jì)算每次合并操作的起始索引 i。每次迭代，i 增加 gap * 2，以確保每次處理的子數(shù)組間隔是 gap。

5. 計(jì)算子數(shù)組邊界：在每次迭代中，計(jì)算兩個(gè)子數(shù)組的起始和結(jié)束索引：begin1、end1 和 begin2、end2。這兩個(gè)子數(shù)組的間隔是 gap。

6. 處理數(shù)組越界：如果 begin2 大于數(shù)組長度 n，循環(huán)將終止。如果 end2 超出了數(shù)組的界限，將其調(diào)整為 n-1。

7. 合并子數(shù)組：使用 while 循環(huán)來合并兩個(gè)子數(shù)組。比較 a[begin1] 和 a[begin2]，將較小的元素復(fù)制到 tmp 數(shù)組中，并相應(yīng)地移動(dòng)索引。當(dāng)一個(gè)子數(shù)組的所有元素都被復(fù)制后，使用另外兩個(gè) while 循環(huán)復(fù)制剩余子數(shù)組中的元素。

8. 拷貝回原數(shù)組：使用 memcpy 將 tmp 中的有序子數(shù)組復(fù)制回原數(shù)組 a。這里，拷貝的區(qū)間是從索引 i 到 end2，拷貝的元素?cái)?shù)量是 end2 - i + 1。

9. 更新間隔：外層循環(huán)的 gap 每次迭代后翻倍，這樣在每次迭代中，處理的子數(shù)組的大小逐漸增加，直到整個(gè)數(shù)組被排序。

非遞歸的歸并排序在某些情況下可能比遞歸版本更有效，因?yàn)樗苊饬诉f歸調(diào)用的開銷，尤其是在深度很大的遞歸樹中。然而，它需要更多的迭代來逐步構(gòu)建有序數(shù)組，因此在實(shí)際應(yīng)用中，選擇哪種實(shí)現(xiàn)取決于具體的需求和場(chǎng)景。

計(jì)數(shù)排序

前言

計(jì)數(shù)排序是速度特別快的一種排序方式，甚至說可以達(dá)到o（n），什么概念，一趟就可以實(shí)現(xiàn)，這是很快的，雖然具備一定的局限性，但是這個(gè)速度也是嘆為觀止的

計(jì)數(shù)排序gif

實(shí)現(xiàn)圖解

這里的核心邏輯就在于，我們需要入數(shù)組和出數(shù)組這兩點(diǎn)

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

//計(jì)數(shù)排序
void Countsort(int* a, int n)
{//求出最小值和最大值int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//計(jì)算差值,需要最小值和最大值//0 1 2三個(gè)數(shù)值，但是2-1=2，也就是兩個(gè)數(shù)值，所以我們需要+1 ,這個(gè)差值也就是我們開辟多大的空間int delta = max - min + 1;//創(chuàng)建數(shù)組空間int* tmp = (int*)calloc(delta, sizeof(int));if (tmp == NULL){perror("Countsort:tmp:err:");exit(1);//正常退出}//把原數(shù)組里面的數(shù)值計(jì)算之后->存放到tmp數(shù)組里面,但是需要控制差值存放在數(shù)組里面for (int i = 0; i < n; i++){tmp[a[i] - min]++;}//從數(shù)組讀取出，放到原數(shù)組里面int j = 0;for (int i = 0; i < delta; i++){while (tmp[i]--){a[j++] = i + min;}}
}

解釋：

1. 求最小值和最大值：

   • 首先初始化?max?和?min?為數(shù)組的第一個(gè)元素的值。
   • 遍歷整個(gè)數(shù)組?a，更新?max?和?min?為數(shù)組中的最大值和最小值。

2. 計(jì)算差值：

   • 計(jì)算最大值和最小值的差值?delta，這個(gè)差值加1后將用于確定計(jì)數(shù)數(shù)組?tmp?的大小。

3. 創(chuàng)建計(jì)數(shù)數(shù)組：

   • 使用?calloc?分配一個(gè)大小為?delta?的數(shù)組?tmp，并將所有元素初始化為0。calloc?會(huì)初始化分配的內(nèi)存為0，這對(duì)于計(jì)數(shù)排序是必要的。

4. 計(jì)數(shù)：

   • 遍歷原數(shù)組?a，對(duì)于數(shù)組中的每個(gè)元素?a[i]，計(jì)算其與最小值?min?的差值，并在?tmp?數(shù)組的相應(yīng)位置增加計(jì)數(shù)。例如，如果?a[i]?是3，且?min?是0，則?tmp[3]?會(huì)增加1。

5. 輸出排序結(jié)果：

   • 使用兩個(gè)指針?i?和?j，i?用于遍歷?tmp?數(shù)組，j?用于指向原數(shù)組?a?的當(dāng)前位置。
   • 對(duì)于?tmp?數(shù)組中的每個(gè)非零元素，將其對(duì)應(yīng)的值加回到原數(shù)組?a?中，直到?tmp[i]?減至0。這意味著將?min + i?賦值給?a[j]，然后?j?增加，重復(fù)這個(gè)過程直到?tmp[i]?為0。

6. 結(jié)束排序：

   • 當(dāng)所有計(jì)數(shù)都減至0時(shí)，原數(shù)組?a?已經(jīng)是部分有序的，排序完成。

7. 錯(cuò)誤處理：

   • 如果?calloc?分配內(nèi)存失敗，使用?perror?打印錯(cuò)誤信息，并調(diào)用?exit?退出程序。

計(jì)數(shù)排序的時(shí)間復(fù)雜度是 O(n + k)，其中 n 是數(shù)組 a 的長度，k 是整數(shù)的范圍（在這個(gè)例子中是 delta）。由于 k 通常遠(yuǎn)小于 n，計(jì)數(shù)排序?qū)τ诖罅繑?shù)據(jù)的排序非常高效。然而，計(jì)數(shù)排序的空間復(fù)雜度也是 O(k)，如果整數(shù)的范圍非常大，它可能需要大量的內(nèi)存。

計(jì)數(shù)排序是一種穩(wěn)定的排序算法，它不會(huì)改變相等元素的相對(duì)順序。它特別適用于當(dāng)數(shù)據(jù)范圍不大且數(shù)據(jù)量很大時(shí)的場(chǎng)景。

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

1. 尋找最大值和最小值：遍歷整個(gè)數(shù)組以找到最大值和最小值，這個(gè)過程的時(shí)間復(fù)雜度是 O(n)，其中 n 是數(shù)組中元素的數(shù)量。

2. 創(chuàng)建計(jì)數(shù)數(shù)組：使用 calloc 為計(jì)數(shù)數(shù)組分配內(nèi)存并初始化，這個(gè)操作的時(shí)間復(fù)雜度是 O(k)，其中 k 是最大值和最小值的差值加 1（即整數(shù)的范圍）。

3. 計(jì)數(shù)：再次遍歷數(shù)組，將每個(gè)元素的計(jì)數(shù)在計(jì)數(shù)數(shù)組中增加。這個(gè)過程的時(shí)間復(fù)雜度也是 O(n)。

4. 輸出排序結(jié)果：最后，根據(jù)計(jì)數(shù)數(shù)組重建排序后的數(shù)組。這個(gè)過程涉及遍歷計(jì)數(shù)數(shù)組，并且對(duì)于每個(gè)非零計(jì)數(shù)，將對(duì)應(yīng)的元素值放入原數(shù)組中。如果計(jì)數(shù)數(shù)組中的非零元素?cái)?shù)量接近 n，則這個(gè)操作的時(shí)間復(fù)雜度接近 O(n)。

綜合上述步驟，計(jì)數(shù)排序的總時(shí)間復(fù)雜度主要由以下兩個(gè) O(n) 操作決定：

• 尋找最大和最小值
• 計(jì)數(shù)和輸出排序結(jié)果

因此，計(jì)數(shù)排序的總時(shí)間復(fù)雜度是 O(n + k)。然而，實(shí)際上，當(dāng) k（整數(shù)的范圍）遠(yuǎn)小于 n 時(shí)，k 可以被視為一個(gè)常數(shù)，所以時(shí)間復(fù)雜度可以簡(jiǎn)化為 O(n)。但是，如果 k 很大，接近或大于 n，時(shí)間復(fù)雜度就接近 O(n + k)。

計(jì)數(shù)排序的空間復(fù)雜度是 O(k)，因?yàn)樾枰~外的計(jì)數(shù)數(shù)組來存儲(chǔ)每個(gè)可能整數(shù)的出現(xiàn)次數(shù)。如果 k 非常大，這可能會(huì)成為一個(gè)問題。

堆排序

前言

堆排序是速度很快的一種排序方式，尤其是處理大數(shù)據(jù)的情況下，這個(gè)堆排序展現(xiàn)了無與倫比的速度，當(dāng)然這里比較吃二叉樹篇章，所以我放在了最后，要是有二叉樹理解不深入的，可以看一下這個(gè)博客，基本上看完之后就沒有問題了

數(shù)據(jù)結(jié)構(gòu)-二叉樹系統(tǒng)性學(xué)習(xí)（四萬字精講拿捏）-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138799868

需要在數(shù)組里面進(jìn)行排序，我們可以采取堆排序?qū)ζ浣鉀Q問題

版本1：

創(chuàng)建一個(gè)數(shù)組等大的堆，把數(shù)組里面的數(shù)值輸入到堆里面進(jìn)行堆排序，但是這樣的弊端就是，不是順序排序

版本2：

每次我們?nèi)《秧斎缓蟠蛴?#xff0c;最后出堆，循環(huán)

弊端就是這樣是時(shí)間復(fù)雜度我們發(fā)現(xiàn)還是o(n)，沒有必要那么麻煩半天時(shí)間復(fù)雜度還是這樣

版本3:（推薦）

在數(shù)組上面進(jìn)行排序，直接輸出順序排序

邏輯講解

1，需要在數(shù)組里面進(jìn)行排序，我們可以采取在數(shù)組建堆

2，然后交換收尾元素，每次調(diào)整的數(shù)值減少1

講解邏輯

首先我們需要知道，

如果我們需要排序的是降序，我們就需要建立小堆

如果我們需要排序的是升序，我們就需要建立大堆

如果我們需要的是升序建立小堆的話

如果我們采取相反的方式的話，就會(huì)導(dǎo)致：（出現(xiàn)兩個(gè)根）

首先n個(gè)數(shù)建小堆，固定第一個(gè)值是最小值
剩下的n-1個(gè)數(shù)再建堆
效率就很差了

如果相反的話，會(huì)導(dǎo)致根節(jié)點(diǎn)變化，從而導(dǎo)致邏輯混亂，數(shù)組里面的數(shù)值少的時(shí)候是不明顯的，但是多的時(shí)候就不行了

邏輯實(shí)現(xiàn)圖解

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

//向下調(diào)整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{int chile = parent * 2 + 1;//循環(huán)條件不能是父親，不然會(huì)導(dǎo)致越界while (chile < n){//三個(gè)孩子進(jìn)行比較if (chile + 1 < n && a[chile] < a[chile + 1]){chile++;}if (a[chile] > a[parent]){Swap(&a[chile], &a[parent]);parent = chile;chile = parent * 2 + 1;}else{break;}}
}
//堆排序數(shù)組內(nèi)進(jìn)行調(diào)整解決
void sort_test(int* a, int sz)
{//放出來的是小堆，所以我們只能排序降序，這樣邏輯更融洽//建堆for (int i = 0; i < sz; i++){AdjustUp(a, i);}//交換排序 把首個(gè)元素和最后一個(gè)交換進(jìn)行排序 每次--while (sz > 0){Swap(&a[0], &a[sz - 1]);AdjustDown(a, sz - 1, 0);sz--;}
}

這個(gè) sort_test 函數(shù)實(shí)現(xiàn)了一個(gè)堆排序算法，它接收一個(gè)整數(shù)數(shù)組 a 和它的大小 sz：

1. 建堆：首先，函數(shù)通過調(diào)用 AdjustUp 函數(shù)來構(gòu)建一個(gè)小頂堆（最小堆）。建堆過程是從最后一個(gè)非葉子節(jié)點(diǎn)開始向上調(diào)整，直到堆頂。

2. 交換和排序：在建堆之后，函數(shù)進(jìn)入一個(gè)循環(huán)，每次循環(huán)中，它將堆頂元素（當(dāng)前堆中的最小元素）與當(dāng)前堆的最后一個(gè)元素交換。然后，堆的大小減少 1，并且對(duì)剩余的堆進(jìn)行向下調(diào)整以保持最小堆性質(zhì)。

3. 循環(huán)結(jié)束：循環(huán)繼續(xù)進(jìn)行，直到堆的大小減小到 0。最終，數(shù)組 a 將被排序?yàn)榻敌?/p>

堆排序衍生的top_k問題

前言

這里本質(zhì)還是堆排序的衍生問題

也就是還是堆排序問題，我們最終需要學(xué)習(xí)的就是處理大型數(shù)據(jù)的問題

?top_k問題時(shí)間復(fù)雜度的計(jì)算

這里提前說明，時(shí)間復(fù)雜度的計(jì)算的目的是來計(jì)算向上調(diào)整的更優(yōu)還是向下調(diào)整更優(yōu)，從肉眼看的話向下調(diào)整優(yōu)于向上調(diào)整，接下來我們進(jìn)行時(shí)間復(fù)雜度的計(jì)算。

此時(shí)我們會(huì)用到等比數(shù)列求和以及裂項(xiàng)相消

首先我們需要我們建堆的時(shí)候是向上調(diào)整，還是向下調(diào)整

如圖詳解

首先我們假設(shè)求的是滿二叉樹，我們求節(jié)點(diǎn)的個(gè)數(shù)

滿二叉樹節(jié)點(diǎn)個(gè)數(shù)

建堆問題：

建堆的話往往的倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)建堆，會(huì)時(shí)間復(fù)雜度最優(yōu)解：也就是

在構(gòu)建堆（尤其是二叉堆）時(shí)，從最后一個(gè)非葉子節(jié)點(diǎn)開始進(jìn)行調(diào)整是時(shí)間復(fù)雜度最優(yōu)解的原因是，這種方法可以減少不必要的調(diào)整操作。

為什么從最后一個(gè)非葉子節(jié)點(diǎn)開始？

1. 葉子節(jié)點(diǎn)：在完全二叉樹中，葉子節(jié)點(diǎn)不包含任何子節(jié)點(diǎn)，因此不需要進(jìn)行調(diào)整。

2. 非葉子節(jié)點(diǎn)：從最后一個(gè)非葉子節(jié)點(diǎn)開始，向上逐個(gè)進(jìn)行調(diào)整，可以確保每個(gè)節(jié)點(diǎn)在調(diào)整時(shí)，其子樹已經(jīng)是堆結(jié)構(gòu)。這樣可以減少調(diào)整的深度，因?yàn)槊總€(gè)節(jié)點(diǎn)最多只需要與其子節(jié)點(diǎn)交換一次。

3. 減少調(diào)整次數(shù)：如果從根節(jié)點(diǎn)開始調(diào)整，那么每個(gè)節(jié)點(diǎn)可能需要多次調(diào)整才能達(dá)到堆的性質(zhì)，特別是那些位于樹底部的節(jié)點(diǎn)。而從底部開始，每個(gè)節(jié)點(diǎn)只需要調(diào)整一次即可。

時(shí)間復(fù)雜度分析

構(gòu)建堆的過程涉及對(duì)每個(gè)非葉子節(jié)點(diǎn)進(jìn)行調(diào)整。對(duì)于一個(gè)具有 𝑛n 個(gè)節(jié)點(diǎn)的完全二叉樹：

• 葉子節(jié)點(diǎn)：有??𝑛/2?個(gè)葉子節(jié)點(diǎn)，它們不需要調(diào)整。

• 非葉子節(jié)點(diǎn)：有??𝑛/2?個(gè)非葉子節(jié)點(diǎn)，需要進(jìn)行調(diào)整。

對(duì)于非葉子節(jié)點(diǎn)，從最后一個(gè)非葉子節(jié)點(diǎn)開始向上調(diào)整，每個(gè)節(jié)點(diǎn)最多只需要進(jìn)行 log?𝑘logk（𝑘k 是節(jié)點(diǎn)的深度）次交換。但是，由于樹的結(jié)構(gòu)，底部的節(jié)點(diǎn)不需要進(jìn)行多次交換，因此整個(gè)調(diào)整過程的時(shí)間復(fù)雜度比 𝑂(𝑛log?𝑛) 要低。

實(shí)際上，構(gòu)建堆的時(shí)間復(fù)雜度是 𝑂(𝑛)，這是因?yàn)?#xff1a;

• 從最后一個(gè)非葉子節(jié)點(diǎn)開始，每個(gè)節(jié)點(diǎn)的調(diào)整次數(shù)與其深度成反比。

• 根節(jié)點(diǎn)的調(diào)整次數(shù)最多，但只需要一次。

• 越往下，節(jié)點(diǎn)的深度越小，但需要調(diào)整的節(jié)點(diǎn)數(shù)量越多。

總結(jié)

從最后一個(gè)非葉子節(jié)點(diǎn)開始建堆，可以確保每個(gè)節(jié)點(diǎn)的調(diào)整次數(shù)與其深度成反比，從而減少總的調(diào)整次數(shù)。這種方法利用了完全二叉樹的性質(zhì)，使得整個(gè)建堆過程的時(shí)間復(fù)雜度達(dá)到最優(yōu)，即 𝑂(𝑛)。這是構(gòu)建堆的最優(yōu)策略，因?yàn)樗钚』吮匾恼{(diào)整操作，從而提高了算法的效率。

建堆復(fù)雜度講解：（向下調(diào)整建堆計(jì)算）

如圖：

這里為什么-2呢，因?yàn)槲覀兊南蛳抡{(diào)整只是調(diào)整h-1層，第h層的節(jié)點(diǎn)的個(gè)數(shù)是2^h-1，所以第h-1層自然就是-2

所以我們發(fā)現(xiàn)，建堆的時(shí)候我們h-1高度的節(jié)點(diǎn)的個(gè)數(shù)相加得出的結(jié)果

為T(n)

所以我們進(jìn)行計(jì)算

從而得出時(shí)間復(fù)雜度，為什么時(shí)間復(fù)雜度是高度，因?yàn)橄蛳抡{(diào)整的時(shí)候，我們循環(huán)終止條件是循環(huán)的高度，也就是當(dāng)父親節(jié)點(diǎn)不小于sz的時(shí)候，所以計(jì)算出高度也就計(jì)算出了時(shí)間復(fù)雜度

建堆復(fù)雜度講解：（向上調(diào)整建堆計(jì)算）?

如圖：

計(jì)算圖解

所以我們得出結(jié)論，這里多了n次

對(duì)比

向上調(diào)整（AdjustUp）和向下調(diào)整（AdjustDown）的時(shí)間復(fù)雜度通常與堆的高度相關(guān)，即 log?𝑘，其中 𝑘k 是堆中元素的數(shù)量。然而，在特定情況下，特別是在構(gòu)建堆的過程中，這些操作的總時(shí)間復(fù)雜度可以是 𝑂(𝑛)，這里的 𝑛?是堆中元素的數(shù)量。

單個(gè)操作的時(shí)間復(fù)雜度：

• 向上調(diào)整 (AdjustUp)：對(duì)于單個(gè)元素，向上調(diào)整的時(shí)間復(fù)雜度是 𝑂(log?𝑘)，因?yàn)樗赡苄枰獜娜~子節(jié)點(diǎn)一直調(diào)整到根節(jié)點(diǎn)，最多涉及 log?𝑘層的比較和交換。

• 向下調(diào)整 (AdjustDown)：同樣，對(duì)于單個(gè)元素，向下調(diào)整的時(shí)間復(fù)雜度也是 𝑂(log?𝑘)，因?yàn)樗赡苄枰獜母?jié)點(diǎn)調(diào)整到葉子節(jié)點(diǎn)，同樣最多涉及 log?𝑘層的比較和交換。

構(gòu)建堆的總時(shí)間復(fù)雜度：

• 當(dāng)我們討論構(gòu)建一個(gè)包含?𝑛?個(gè)元素的堆時(shí)，所有元素的向上調(diào)整操作的總時(shí)間復(fù)雜度是?𝑂(𝑛)。這是因?yàn)?#xff1a;

  • 樹的非葉子節(jié)點(diǎn)大約是?𝑛/2（因?yàn)槿~子節(jié)點(diǎn)也是?𝑛/2 左右）。

  • 每個(gè)非葉子節(jié)點(diǎn)的調(diào)整操作最多涉及?log?𝑘 的時(shí)間，但是由于樹的結(jié)構(gòu)，從根到葉的路徑上的節(jié)點(diǎn)數(shù)量總和大致是?𝑛n。

  • 因此，所有節(jié)點(diǎn)的向上調(diào)整操作加起來的時(shí)間復(fù)雜度是?𝑂(𝑛)。

為什么是?𝑂(𝑛) 而不是?𝑂(𝑛log?𝑘)？

• 樹的結(jié)構(gòu)特性：在完全二叉樹中，每個(gè)層級(jí)的節(jié)點(diǎn)數(shù)量是指數(shù)增長的。從根節(jié)點(diǎn)（1個(gè)節(jié)點(diǎn)）到第二層（2個(gè)節(jié)點(diǎn)），再到第三層（4個(gè)節(jié)點(diǎn)），等等。因此，較低層級(jí)的節(jié)點(diǎn)數(shù)量遠(yuǎn)多于較高層級(jí)的節(jié)點(diǎn)數(shù)量。

• 調(diào)整深度：根節(jié)點(diǎn)的調(diào)整可能需要?log?𝑘 的時(shí)間，但較低層級(jí)的節(jié)點(diǎn)只需要較少的調(diào)整時(shí)間。由于底部層級(jí)的節(jié)點(diǎn)數(shù)量較多，它們較短的調(diào)整時(shí)間在總體上對(duì)總時(shí)間復(fù)雜度的貢獻(xiàn)較小。

總結(jié)：

• 對(duì)于單個(gè)元素，向上調(diào)整和向下調(diào)整的時(shí)間復(fù)雜度是?𝑂(log?𝑘)

• 在構(gòu)建堆的過程中，所有元素的向上調(diào)整操作的總時(shí)間復(fù)雜度是?𝑂(𝑛)，而不是?𝑂(𝑛log?𝑘)，這是由于完全二叉樹的結(jié)構(gòu)特性和調(diào)整操作的分布。

因此，向上調(diào)整和向下調(diào)整在構(gòu)建堆的過程中的總時(shí)間復(fù)雜度是 𝑂(𝑛)，而不是 𝑂(log?𝑛)。這個(gè)線性時(shí)間復(fù)雜度是構(gòu)建堆算法的一個(gè)重要特性，使得它在處理大量數(shù)據(jù)時(shí)非常高效。

向上調(diào)整和向下調(diào)整雖然最后計(jì)算的都是O(N)

但是滿二叉樹最后一層占據(jù)一半的節(jié)點(diǎn)

所以我們得出結(jié)論，向下調(diào)整的復(fù)雜度優(yōu)于向上調(diào)整的復(fù)雜度

top_k問題的實(shí)現(xiàn)邏輯

1，首先我們創(chuàng)建一個(gè)文件，寫入隨機(jī)數(shù)值1000w個(gè)

2，如果需要讀取文件里面最大的10個(gè)數(shù)值，那么我們就需要，創(chuàng)建一個(gè)小堆

原因：

這樣的話，輸入數(shù)值的時(shí)候，如果讀取的數(shù)值比堆頂大，就會(huì)替換堆頂從而進(jìn)堆，然后進(jìn)行堆排序。

3，在讀取文件的時(shí)候，我們需要讀取一個(gè)接收一個(gè)，然后進(jìn)行數(shù)值的對(duì)比，從而進(jìn)行交換。

4，最后打印最大的數(shù)值

5，備注：我們?nèi)绾闻袛辔覀兊恼业降淖畲蟮那笆畟€(gè)數(shù)值的正確的，

也是很簡(jiǎn)單的，我們?cè)O(shè)定的隨機(jī)數(shù)值是10000以內(nèi)的，然后設(shè)定完之后，我們不調(diào)用，進(jìn)入TXT里面更改一些數(shù)值。設(shè)定一些大于一萬的數(shù)值，此時(shí)我們就可以發(fā)現(xiàn)我們篩選的數(shù)值對(duì)不對(duì)。

當(dāng)然如果我們需要找最小的數(shù)值，那么我們?cè)O(shè)定數(shù)值最好為-1，因?yàn)槭f個(gè)數(shù)值，很可能是有很多0的。但是我們?nèi)庋劭床怀鰜怼?/strong>

top_k計(jì)算的代碼實(shí)現(xiàn)

//進(jìn)行計(jì)算
void TOP_K()
{int k = 10;//scanf("%d", &k);FILE* ps = fopen("data.txt", "r");if (ps == NULL){perror("Error:opening:file");exit(1);}//創(chuàng)建空間存儲(chǔ)int* tmp = (int*)malloc(sizeof(int) * k);if (tmp == NULL){perror("TOP_K():Heap* tmp:error");exit(1);}//讀取個(gè)數(shù)for (int i = 0; i < 10; i++){fscanf(ps, "%d", &tmp[i]);}// 建堆,從最后一個(gè)非葉子節(jié)點(diǎn)開始建堆,// 這里的 -1-1 實(shí)際上看起來像是一個(gè)錯(cuò)誤。// 通常，當(dāng)我們需要找到最后一個(gè)非葉子節(jié)點(diǎn)的索引以開始建堆過程時(shí)，我們會(huì)從倒數(shù)第二個(gè)節(jié)點(diǎn)開始（因?yàn)閿?shù)組索引從0開始）。對(duì)于大小為 k 的數(shù)組，最后一個(gè)非葉子節(jié)點(diǎn)的索引計(jì)算如下：// 簡(jiǎn)單的說就是，k是數(shù)值，我們需要傳參傳遞是下標(biāo)，找到父親節(jié)點(diǎn)需要減去1 除以2 所以就有了-2的情況for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(tmp, k, i);}//排序int val = 0;int ret = fscanf(ps, "%d", &val);while (ret != EOF){if (tmp[0] < val){tmp[0] = val;AdjustDown(tmp, k, 0);}ret = fscanf(ps, "%d", &val);}//打印for (int i = 0; i < k; i++){printf("%d ", tmp[i]);}fclose(ps);}

top_k完整代碼

//TOP_K問題的實(shí)現(xiàn) 小堆尋找最大值
//創(chuàng)建隨機(jī)數(shù)值
void TOP_K_fopen_w()
{FILE* ps = fopen("data.txt", "w");if (ps == NULL){perror("FILE* ps :fopen:error");exit(1);}srand(time(0));for (int i = 0; i < 100000; i++){int s = rand() % 10000;fprintf(ps, "%d\n", s);}fclose(ps);
}
//進(jìn)行計(jì)算
void TOP_K()
{int k = 10;//scanf("%d", &k);FILE* ps = fopen("data.txt", "r");if (ps == NULL){perror("Error:opening:file");exit(1);}//創(chuàng)建空間存儲(chǔ)int* tmp = (int*)malloc(sizeof(int) * k);if (tmp == NULL){perror("TOP_K():Heap* tmp:error");exit(1);}//讀取個(gè)數(shù)for (int i = 0; i < 10; i++){fscanf(ps, "%d", &tmp[i]);}// 建堆,從最后一個(gè)非葉子節(jié)點(diǎn)開始建堆,// 這里的 -1-1 實(shí)際上看起來像是一個(gè)錯(cuò)誤。// 通常，當(dāng)我們需要找到最后一個(gè)非葉子節(jié)點(diǎn)的索引以開始建堆過程時(shí)，我們會(huì)從倒數(shù)第二個(gè)節(jié)點(diǎn)開始（因?yàn)閿?shù)組索引從0開始）。對(duì)于大小為 k 的數(shù)組，最后一個(gè)非葉子節(jié)點(diǎn)的索引計(jì)算如下：// 簡(jiǎn)單的說就是，k是數(shù)值，我們需要傳參傳遞是下標(biāo)，找到父親節(jié)點(diǎn)需要減去1 除以2 所以就有了-2的情況for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(tmp, k, i);}//排序int val = 0;int ret = fscanf(ps, "%d", &val);while (ret != EOF){if (tmp[0] < val){tmp[0] = val;AdjustDown(tmp, k, 0);}ret = fscanf(ps, "%d", &val);}//打印for (int i = 0; i < k; i++){printf("%d ", tmp[i]);}fclose(ps);}

解釋：

1. TOP_K_fopen_w 函數(shù)：

   • 這個(gè)函數(shù)用于生成隨機(jī)數(shù)據(jù)并寫入到 "data.txt" 文件中。
   • 使用?fopen?打開文件，如果失敗則打印錯(cuò)誤并退出程序。
   • 使用?srand?和?time?初始化隨機(jī)數(shù)生成器的種子。
   • 循環(huán)生成100000個(gè)0到9999之間的隨機(jī)整數(shù)，并使用?fprintf?將它們寫入文件，每個(gè)數(shù)字一行。
   • 最后使用?fclose?關(guān)閉文件。

2. TOP_K 函數(shù)：

   • 首先定義了要找出的最大的數(shù)的個(gè)數(shù)?k（這里設(shè)置為10）。
   • 使用?fopen?打開 "data.txt" 文件進(jìn)行讀取，如果失敗則打印錯(cuò)誤并退出程序。
   • 分配一個(gè)大小為?k?的數(shù)組?tmp?用于存儲(chǔ)小頂堆的元素。
   • 讀取前10個(gè)數(shù)字存入?tmp?數(shù)組中，這里假設(shè)文件中的數(shù)字至少有10個(gè)。

3. 建堆：

   • 從最后一個(gè)非葉子節(jié)點(diǎn)開始調(diào)整堆，以確保?tmp?數(shù)組是一個(gè)有效的小頂堆。這里的注釋提到 "-1-1 實(shí)際上看起來像是一個(gè)錯(cuò)誤"，但實(shí)際上，計(jì)算最后一個(gè)非葉子節(jié)點(diǎn)的索引是正確的。對(duì)于大小為?k?的完全二叉樹，最后一個(gè)非葉子節(jié)點(diǎn)的索引是?(k - 2) / 2。這里的計(jì)算?(k - 1 - 1) / 2?實(shí)際上得到的是倒數(shù)第二個(gè)非葉子節(jié)點(diǎn)的索引
   • 使用?AdjustDown?函數(shù)從最后一個(gè)非葉子節(jié)點(diǎn)開始向下調(diào)整堆，確保堆的性質(zhì)。

4. 排序：

   • 使用?fscanf?從文件中讀取數(shù)字，直到文件結(jié)束（EOF）。
   • 對(duì)于每個(gè)讀取的數(shù)字，如果它大于堆頂（即?tmp[0]），則替換堆頂元素，并調(diào)用?AdjustDown?函數(shù)向下調(diào)整堆。
   • 這個(gè)過程確保了?tmp?數(shù)組中始終存儲(chǔ)著當(dāng)前讀取到的最大的K個(gè)數(shù)。

5. 打印結(jié)果：

   • 循環(huán)打印?tmp?數(shù)組中的所有元素，這些元素就是最大的K個(gè)數(shù)。
   • 使用?fclose?關(guān)閉文件。

6. 注意：

   • 代碼中沒有提供?AdjustDown?函數(shù)的實(shí)現(xiàn)，這個(gè)函數(shù)用于向下調(diào)整堆，以保持堆的性質(zhì)。
   • 代碼假設(shè)文件中的數(shù)字?jǐn)?shù)量至少為10，如果少于10個(gè)，需要額外的錯(cuò)誤處理。
   • 代碼中沒有考慮內(nèi)存分配失敗的情況，實(shí)際使用中應(yīng)該檢查?malloc?的返回值。

整體上，這段代碼展示了如何使用小頂堆來解決TOP-K問題，通過維護(hù)一個(gè)大小為K的最小堆，可以有效地找到數(shù)據(jù)流中最大的K個(gè)數(shù)。