手機視頻網站怎么做保定seo推廣公司
前言
1，數據結構排序篇章是一個大的工程，這里是一個總結篇章，配備動圖和過程詳解，從難到易逐步解析。
2，這里我們詳細分析幾個具備教學意義和實際使用意義的排序：
冒泡排序，選擇排序，插入排序，希爾排序，快排（遞歸，霍爾版本），快排（遞歸，前后指針版本），快排（非遞歸版本），堆排序（解決top_k問題），歸并排序（遞歸），歸并排序（非遞歸），計數排序
3，這里我想說一下，學習排序之前需要了解一些相關的知識，
- 復雜度：目的是了解算法的時間復雜度，復雜度精講（時間+空間）-CSDN博客
https://blog.csdn.net/Jason_from_China/article/details/138073981
- 棧和隊列：目的是在排序非遞歸實現(xiàn)里面，我們需要用到棧，比如速排的非遞歸實現(xiàn)，數據結構-棧和隊列(速通版本)-CSDN博客
- 二叉樹：目的是在排序計算里面，遞歸的解決方式是比較常用的方式，二叉樹正好是用遞歸來完成的，可以輔助我們深入的了解一下排序的遞歸數據結構-二叉樹系統(tǒng)性學習（四萬字精講拿捏）-CSDN博客
4，當然最后一點就是這些知識也可以不直接涉及到，如果你的時間比較緊張的話，只是理解起來相對而言需要一點難度，這些知識不是必須的。需要知道的是，這些知識可以幫助你深入理解排序的邏輯。
5，對于排序的學習很重要的一點就是，每次實現(xiàn)的時候我們往往需要先實現(xiàn)單趟排序的實現(xiàn)，之后再實現(xiàn)多趟的完結，這個是很重要的思路
6，這里的代碼觀看，尤其是對于排序代碼的實現(xiàn)
- 先看內循環(huán)，因為內循環(huán)是單趟實現(xiàn)
- 再看外循環(huán)，因為外循環(huán)是全部實現(xiàn)邏輯。
- 這里一定不能搞錯順序，不然數據結構排序篇章很容易就無法看懂。
- 并且單趟實現(xiàn)往往重于多趟實現(xiàn)，因為多趟實現(xiàn)往往是單趟循環(huán)的循環(huán)和重復
冒泡排序
前言
冒泡排序具備很強的教學意義，但是沒有什么實踐意義，這里作為第一個講解的排序，目的是從簡單開始講解，方便理解
冒泡排序gif
冒泡排序單趟實現(xiàn)
冒泡排序一次只解決一個數字，交換一個數字之后，開始交換第二個數字
那么多趟實現(xiàn)就直接for循環(huán)多趟實現(xiàn)就可以了
冒泡排序多趟實現(xiàn)邏輯
舉例2（無法理解可以先不看舉例2，這里是參照組）：
假設初始數組： [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] (數組已經排序完成)
冒泡排序注意事項
單趟循環(huán)需要注意事項
這里如果傳參如果傳遞是是n，那么單趟實現(xiàn)的時候，我們不能循環(huán)n次數，只能循環(huán)n-1次數，因為
多趟循環(huán)需要注意事項
冒泡排序的交換邏輯
冒泡排序代碼實現(xiàn)
//交換函數 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]);}}} }解釋：
交換函數（Swap）：
- 函數原型：
void Swap(int* p1, int* p2)- 參數：
p1?和?p2?是指向兩個整數的指針。- 功能：交換兩個指針所指向的整數的值。
- 實現(xiàn)：首先，使用一個臨時變量?
tmp?存儲?p1?指向的值。然后將?p2?指向的值賦給?p1?指向的位置，最后將臨時變量?tmp（原來?p1?的值）賦給?p2?指向的位置。冒泡排序（BubbleSort）：
- 函數原型：
void BubbleSort(int* a, int n)- 參數：
a?是指向整數數組的指針，n?是數組中元素的數量。- 功能：對數組?
a?進行原地排序，使數組中的元素按照非遞減順序排列。- 實現(xiàn)：冒泡排序通過重復遍歷要排序的數組，比較相鄰元素，如果它們的順序錯誤就把它們交換過來。遍歷數組的工作是在外層循環(huán)中完成的，內層循環(huán)負責實際的比較和交換。
- 交換函數就是一個交換函數，因為后面我還需要調用，所以這里我單獨拿出來。
冒泡排序時間復雜度計算
冒泡排序的時間復雜度計算基于算法執(zhí)行的比較和交換操作的次數。下面是冒泡排序的時間復雜度分析：
最佳情況：當數組已經完全有序時，冒泡排序只需要進行一次遍歷即可確定數組已經有序，不需要進行任何交換。在這種情況下，時間復雜度是 O(n)，其中 n 是數組的長度。
平均情況和最壞情況：在平均情況和最壞情況下，冒泡排序需要進行 n-1 次遍歷，每次遍歷中進行的比較次數依次減少。具體來說：
- 第一次遍歷最多進行 n-1 次比較。
- 第二次遍歷最多進行 n-2 次比較。
- ...
- 最后一次遍歷進行 1 次比較。
總的比較次數可以表示為：(n-1) + (n-2) + ... + 1。這是一個等差數列求和問題，其和為 n(n-1)/2。因此，平均情況和最壞情況下的時間復雜度是 O(n^2)。
空間復雜度：冒泡排序是原地排序算法，它不需要額外的存儲空間來創(chuàng)建另一個數組，只需要一個臨時變量用于交換元素。因此，冒泡排序的空間復雜度是 O(1)。
穩(wěn)定性：冒泡排序是穩(wěn)定的排序算法，因為它不會改變相同元素之間的相對順序。
總結來說，冒泡排序的時間復雜度是：
- 最佳情況：O(n)
- 平均情況：O(n^2)
- 最壞情況：O(n^2)
由于冒泡排序在大多數情況下效率不高，特別是對于大數據集，它通常不作為首選排序算法。然而，它的簡單性和穩(wěn)定性使其在某些特定情況下（如小數據集或基本有序的數據）仍然有用。
直接選擇排序
前言
直接選擇排序也是一個比較簡單的排序，所以這里放在第二個進行講解，這里和冒泡排序是有一點相似。直接選擇排序和冒泡排序一樣，也是具備一定的教學意義，但是沒有什么實際操作的意義，因為直接選擇排序的時間復雜度比較高，書寫起來和插入排序又差不多，所以沒有必要寫直接選擇排序。
直接選擇排序gif
直接選擇排序單趟實現(xiàn)
1，初始化min（最小值）=0（也就是最左邊的下標）的元素為最小值
2，遍歷數組，如果此時出現(xiàn)更小的元素，這個元素的下標是i，那么我們設定min=i
3，之后交換最左邊的元素和數值最小元素，因為這個時候我們已經找到下標了
4，最后排序好的最小值放在了最左邊，那么此時最左邊所在位置不需要進行排序了，分離出來就可以
5，這里因為選擇排序效率太低了 ，我們稍微進階一下，我們從兩側開始，選出最小和最大，從而進行交換，雖然沒有提高多少效率，但是還是比之前的速度快兩倍
直接選擇排序注意事項
1，這里begin和end都是外層循環(huán)，也就是隨著++和--進行縮小差距
2，這里begin和end不是索引，而是縮小差距用的
3，這里是mini和maxi是索引
4，最后交換的時候交換的是下標的元素，不是下標
直接選擇排序多趟實現(xiàn)圖解
直接選擇排序代碼實現(xiàn)
//交換函數 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++){//找到最小值，賦值下標if (a[i] < a[mini]){mini = i;}//找到最小值，賦值下標if (a[i] > a[maxi]){maxi = i;}}//把最小值和最大值放到開頭和結尾去Swap(&a[mini], &a[begin]);Swap(&a[maxi], &a[end]);begin++; end--;} }解釋：
- 外層循環(huán)從索引0開始，直到倒數第二個元素。
- 在每次外層循環(huán)中，假設當前索引位置的元素是未排序部分的最小值。
- 內層循環(huán)從外層循環(huán)的下一個位置開始，遍歷未排序部分的元素，尋找最小值的索引
minIndex。- 如果找到的最小值不在當前索引位置，使用
Swap函數將其交換到當前索引位置。- 這樣，每次外層循環(huán)結束時，未排序部分的最小值都被移動到了排序好的部分的末尾。
注意：
- 直接選擇排序不是穩(wěn)定的排序算法，即相等元素之間的相對順序可能會改變。
- 直接選擇排序的時間復雜度是O(n^2)，在大多數情況下，它不如其他更高效的排序算法。
- 直接選擇排序的空間復雜度是O(1)，因為它是原地排序算法。
選擇排序時間復雜度計算
外層循環(huán)：選擇排序算法有一個外層循環(huán)，它從第一個元素遍歷到倒數第二個元素。這個循環(huán)執(zhí)行了 n?1 次，其中 n 是數組的長度。
內層循環(huán)：對于外層循環(huán)的每一次迭代，都有一個內層循環(huán)，它從當前考慮的元素之后的第一個元素遍歷到數組的最后一個元素。在第一次外層循環(huán)迭代時，內層循環(huán)執(zhí)行 n?1 次；在第二次迭代時，執(zhí)行n?2 次；依此類推，直到最后一次迭代，只執(zhí)行一次。
總迭代次數：內層循環(huán)的總迭代次數可以表示為一個等差數列之和： (𝑛?1)+(𝑛?2)+…+2+1=n(n?1)?/2
時間復雜度：由于外層循環(huán)和內層循環(huán)的迭代次數都是 Θ(𝑛)（即線性關系），因此選擇排序的總時間復雜度是 Θ(𝑛^2)。
空間復雜度：選擇排序是原地排序算法，它只需要一個額外的變量來存儲最小元素的索引，因此空間復雜度是 Θ(1)。
插入排序
前言
插入排序是很重要的排序，著名的希爾排序就是從插入排序演變過來的，所以我們需要并且很多時候有些面試也是會面試插入排序的，所以需要好好捋清楚插入排序的邏輯是什么
插入排序gif
插入排序單趟實現(xiàn)
1，插入排序我們需要假設最后一個數值也就是end+1是需要排序的，其他都是排序好的
2，把end+1這個下標的數值存放在tmp里面，并且和前面進行比較
3，如果遇見的元素比tmp大，我們繼續(xù)往前移動進行比較，同時a[end]=a[end+1]往后覆蓋
4，當遇見的是比tmp小的數值的時候，此時我們找到了tmp數值應該在的位置，進行插入
插入排序注意事項
這里需要注意的關鍵也是區(qū)間問題，假設數組有n個，那么end就是倒數第二個下標，end+1就是最后一個下標，是為了防止越界
我們需要小于n-1，因為，end=n-1；end+1=n，那么就越界了
所以在循環(huán)最大值里面，end=i=n-2,；end+1=n-1（最后一個數值）
插入排序代碼的實現(xiàn)
//插入排序 void InsertionSort(int* a, int n) {//多趟實現(xiàn),這里n的截止條件-1，是因為下標從n-1就結束了，//不過我們需要小于n-1，因為，end=n-1；end+1=n，那么就越界了for (int i = 0; i < n - 1; i++){//單趟實現(xiàn)int end = i; int tmp = a[end + 1];while (end >= 0){//判斷是不是比前一個數值小，小的話就往前走，不小的話停下來進行賦值if (tmp < a[end]){a[end + 1] = a[end];end--;}else//找到了，此時跳出循環(huán)就可以{break;}}//這里是很多人會搞混亂的一點，//因為是找到了，所以end還沒有繼續(xù)移動，但是end+1+1的元素已經移動，所以end+1的位置是tmp應該出現(xiàn)的位置a[end + 1] = tmp;} }解釋：
函數
InsertionSort接受兩個參數：一個指向整數數組a的指針和數組的長度n。外層循環(huán)從索引
0遍歷到n-1。每次迭代，i代表已排序部分的最后一個元素的索引。在外層循環(huán)的每次迭代中，
end變量被設置為當前索引i，表示當前考慮的元素的索引。tmp變量存儲了a[i + 1]的值，這是未排序的第一個元素，也是我們準備插入到已排序部分的元素。內層
while循環(huán)用于在已排序部分從后向前掃描，找到tmp應該插入的位置。end變量隨著比較逐步遞減。在
while循環(huán)中，如果tmp小于當前比較的元素a[end]，則將a[end]向后移動一個位置，為tmp騰出空間。如果
tmp大于或等于a[end]，則while循環(huán)通過break語句結束，找到了tmp應該插入的位置。循環(huán)結束后，將
tmp賦值給a[end + 1]，完成插入操作。這個過程重復進行，直到數組中的所有元素都被掃描并插入到正確的位置。
代碼邏輯：
- 插入排序的基本思想是，對于數組中的每個元素，將其插入到前面已經排好序的子數組中的正確位置。
- 初始時，認為數組的第一個元素是已排序的。然后，從第二個元素開始，逐個插入到前面的已排序序列中。
- 每次插入操作都需要將元素與已排序序列中的元素進行比較，直到找到合適的插入點。
注意：
- 這段代碼在插入元素時，如果插入點是數組的開始，那么不需要進行任何移動操作，直接插入即可。
- 代碼中的
end變量用于記錄當前比較的元素在數組中的位置，而tmp變量用于暫存當前要插入的元素。- 插入排序是穩(wěn)定的排序算法，因為它不會改變相等元素的相對順序。
性能：
- 插入排序的平均時間復雜度和最壞時間復雜度都是?𝑂(𝑛^2)，其中?n?是數組的長度。
- 插入排序的空間復雜度是?𝑂(1)，因為它是原地排序算法，不需要額外的存儲空間。
插入排序的時間復雜度
插入排序算法的時間復雜度取決于數組的初始順序，具體如下：
最佳情況：如果輸入數組已經是完全有序的，插入排序只需要進行 n 次比較（每次比較后插入一個元素到已排序部分），而不需要進行任何交換。在這種情況下，時間復雜度是O(n)。
平均情況：在平均情況下，插入排序的時間復雜度是 O(n^2)。這是因為每個元素都需要與已排序部分的多個元素進行比較，平均下來，每個元素需要比較n/2次。
最壞情況：如果輸入數組是完全逆序的，插入排序需要進行n(n?1)?/2次比較和 n(n?1)?/2次交換，時間復雜度是 O(n^2)。
空間復雜度：插入排序是原地排序算法，它只需要一個額外的存儲空間來暫存當前比較的元素，因此空間復雜度是 O(1)。
穩(wěn)定性：插入排序是穩(wěn)定的排序算法，它保持了相等元素的原始順序。
時間復雜度的詳細分析：
- 插入排序通過構建有序序列來工作，對于未排序的數據，在已排序的序列中從后向前掃描，找到相應位置并插入。
- 在每次迭代中，算法將當前元素與已排序序列中的元素逐一比較，找到合適的插入點。
- 對于每個元素，比較操作可能需要進行?i?次（其中?𝑖i?是當前元素在數組中的位置），從第一個元素到最后一個元素，所需比較的總次數是遞增的。
時間復雜度的數學表達式是：
總比較次數=1+2+3+…+(𝑛?1)=𝑛(𝑛?1)/2總比較次數
這表明插入排序的時間復雜度是 Θ(𝑛^2),盡管在最壞情況下時間復雜度較高，插入排序對于小規(guī)模數據集或部分有序的數據集來說是非常高效的。
希爾排序
前言
從希爾開始，排序的速度就開始上升了，這里的排序開始上一個難度了，當然難一點的排序其實也不是很難，當你對于插入排序了解的足夠深入的時候，你會發(fā)現(xiàn)其實希爾就是插入的異形，但是本質上還是一樣的
希爾排序gif
希爾排序單趟實現(xiàn)
1，希爾排序本質就是插入排序的進化，插入排序是尋找比較進行插入，希爾這個人覺得插入排序有點慢，就覺得我們可不可以進行預排序，也就是數值原來是0-9的情況下，最壞的情況我們需要循環(huán)9次數才能找到需要插入的點在哪，那么此時我們能不能進行一個預排序
2，所謂的預排序就是，我們假設幾個為一組，幾個為一組，這個組的變量我們設置為gap。假設處置3個為一組，那么gap=3
3，此時我們可以把這一組，先采取插入排序的方式進行預排序，預排序之后我們就會發(fā)現(xiàn)這一組的這條線上的數值已經有序
4，多趟實現(xiàn)只是反復的實現(xiàn)第一趟的實現(xiàn)的邏輯
希爾排序的多趟實現(xiàn)
1，多趟實現(xiàn)只是反復的實現(xiàn)第一趟的實現(xiàn)的邏輯
2，我們需要先知道單趟遍歷的時候，我們需要假設gap一組的，這個中間的元素是沒有的，那么此時此時一組就是兩個數值，我們需要讓這兩個數值進行交換
3，這兩個數值交換之后我們這個時候需要循環(huán)開始插入排序的邏輯，也就是假設前面的兩個數值是已經有序的，那么新插入的一個數值是需要排序的，我們進行排序
4，一趟結束之后，我們繼續(xù)多趟實現(xiàn)，這幾個數值繼續(xù)預排序
5，繼續(xù)預排序
6，此時gap=3，那么我們繼續(xù)，gap/2=1，之后繼續(xù)進行預排序，此時我們就得到了這個排序正確的數值
希爾排序代碼的實現(xiàn)-版本1
//希爾排序 void ShellSort(int* a, int n) {int gap = n - 1;//定義gap,這里循環(huán)停止的條件是>1，原因是+1了，已經恒大于0了，所以需要大于1，等于都不可以while (gap > 1){gap = gap / 3 + 1;//循環(huán)實現(xiàn)每一組for (int j = 0; j < gap; j++){//gap單趟實現(xiàn)for (int i = j; i < n - gap; i += gap){int end = i; int tmp = a[end + gap];//一組的實現(xiàn)while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//交換找到的數值a[end + gap] = tmp;}}} }?解釋：
函數
ShellSort接受兩個參數：一個指向整數數組a的指針和數組的長度n。初始化間隔
gap為數組長度n - 1，這是希爾排序開始時的最大間隔。
while循環(huán)用于逐步減小間隔，直到間隔為1。當gap大于1時，循環(huán)繼續(xù)。在每次
while循環(huán)的開始，重新計算間隔gap。這里使用的是gap = gap / 3 + 1，這是一種常見的間隔序列，由Donald Shell提出。外層
for循環(huán)用于遍歷數組，步長為當前的間隔gap。內層
for循環(huán)用于實現(xiàn)插入排序，但僅限于間隔gap內的范圍。在內層循環(huán)中，
end變量記錄當前考慮的元素的索引，tmp變量暫存當前要插入的元素。
while循環(huán)用于在間隔gap內從后向前掃描，找到tmp應該插入的位置。如果
tmp小于當前比較的元素a[end]，則將a[end]向后移動一個間隔gap的距離，為tmp騰出空間。如果
tmp大于或等于a[end]，則while循環(huán)結束，找到了tmp應該插入的位置。循環(huán)結束后，將
tmp賦值給a[end + gap]，完成插入操作。這個過程重復進行，直到數組中的所有元素都被掃描并插入到正確的位置。
代碼邏輯：
- 希爾排序通過多個插入排序的變體來工作，每個變體都有一個特定的間隔。
- 初始時，間隔較大，排序的穩(wěn)定性較差，但可以快速減少無序度。
- 隨著間隔逐漸減小，排序的穩(wěn)定性逐漸提高，最終當間隔為1時，算法變?yōu)槠胀ǖ牟迦肱判?#xff0c;確保數組完全有序。
注意：
- 希爾排序不是穩(wěn)定的排序算法，因為它可能會改變相等元素的相對順序。
- 希爾排序的時間復雜度通常在?𝑂(𝑛log?𝑛) 和?𝑂(𝑛^2)?之間，具體取決于間隔序列的選擇。
- 希爾排序的空間復雜度是?𝑂(1，因為它是原地排序算法，不需要額外的存儲空間。
希爾排序代碼的實現(xiàn)-版本2
上面那個代碼一般是教學使用，書寫會更加詳細理解，但是很多書本會這樣寫
這里的關鍵在于，不再進行先一組排序結束，再反過來進行下一組反復執(zhí)行
而是直接這一組實現(xiàn)完畢之后，++，直接進行下一組的實現(xiàn)，本質上還是一樣的
只是直接這樣書寫，容易不理解
//希爾排序 void ShellSort02(int* a, int n) {int gap = n - 1;//定義gap,這里循環(huán)停止的條件是>1，原因是+1了，已經恒大于0了，所以需要大于1，等于都不可以while (gap > 1){gap = gap / 3 + 1;//循環(huán)實現(xiàn)每一組+//gap單趟實現(xiàn)for (int i = 0; i < n - gap; i++){int end = i; int tmp = a[end + gap];//一組的實現(xiàn)while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//交換找到的數值a[end + gap] = tmp;}} }解釋：
函數
ShellSort02接受兩個參數：一個指向整數數組a的指針和數組的長度n。初始化間隔
gap為數組的最后一個索引n - 1。
while循環(huán)用于逐步減小間隔，直到間隔小于或等于1。循環(huán)的條件是gap > 1，這是因為間隔在每次迭代中都會減小，所以不需要檢查gap == 1的情況。在
while循環(huán)內部，重新計算間隔gap。這里使用的計算方法是gap = gap / 3 + 1，這是一種常見的間隔序列，旨在逐步減小間隔，直到達到1。外層
for循環(huán)遍歷數組，直到i < n - gap，即遍歷到數組的末尾減去當前間隔的位置。在外層
for循環(huán)中，end變量記錄當前考慮的元素的索引，tmp變量暫存當前間隔位置的元素值。內層
while循環(huán)用于在數組中找到tmp應該插入的位置。它從當前索引end開始，向前以間隔gap的距離進行比較。如果
tmp小于當前比較的元素a[end]，則將a[end]向后移動一個間隔gap的距離，為tmp騰出空間。如果
tmp大于或等于a[end]，則while循環(huán)結束，找到了tmp應該插入的位置。循環(huán)結束后，將
tmp賦值給a[end + gap]，完成插入操作。這個過程重復進行，直到數組中的所有元素都被掃描并插入到正確的位置。
代碼邏輯：
- 希爾排序通過多個插入排序的變體來工作，每個變體都有一個特定的間隔。
- 初始時，間隔較大，隨著算法的進行，間隔逐漸減小，直到變?yōu)?，此時算法變?yōu)槠胀ǖ牟迦肱判颉?/li>
- 通過逐步減小間隔，希爾排序能夠在每次迭代中對數組的更大范圍內的元素進行排序，從而減少比較和移動的次數。
希爾排序gap的界定
一般來說，一組為多少這個不好說，希爾開始書寫的時候，gap是/2,來進行書寫的，但是被認為效率最高的是，除以3+1，但是/3+1有一個弊端就是這個是恒大于0的，所以終止條件應該換為大于1就繼續(xù)循環(huán)，小于等于1就停止循環(huán)
希爾排序的時間復雜度
希爾排序的時間復雜度取決于所選擇的間隔序列，它通常介于以下范圍：
最好情況：對于某些特定的間隔序列，希爾排序可以達到O(nlogn) 的時間復雜度，這與快速排序或歸并排序相當。
平均情況：平均情況下，希爾排序的時間復雜度通常被認為是 O(n(logn)2)，這比=O(nlogn) 稍差，但仍然比普通插入排序的 𝑂(𝑛^2) 好得多。
最壞情況：最壞情況下，希爾排序的時間復雜度可以退化到𝑂(𝑛^2)，這通常發(fā)生在間隔序列選擇不佳時。
實際性能：在實際應用中，希爾排序的性能通常比普通插入排序好，但不如快速排序、堆排序或歸并排序。它的實際性能還取決于數據的初始狀態(tài)和間隔序列的選擇。
間隔序列的影響：不同的間隔序列對希爾排序的性能有很大影響。例如，使用Hibbard 間隔序列或Sedgewick間隔序列可以提高性能，有時甚至可以達到接近 O(nlogn) 的效率。
空間復雜度：希爾排序是原地排序算法，其空間復雜度為 𝑂(1)。
穩(wěn)定性：希爾排序不是穩(wěn)定的排序算法，這意味著相等的元素在排序后可能會改變它們原來的順序。
總的來說，希爾排序是一種有效的排序算法，特別是對于中等大小的數據集或者當數據已經部分有序時。然而，對于大型數據集，通常推薦使用其他更高效的排序算法，如快速排序、堆排序或歸并排序。
快排（霍爾版本-遞歸解決）
前言
快排是很重要的排序，也是一種比較難以理解的排序，這里我們會用遞歸的方式和非遞歸的方式來解決，遞歸來解決是比較簡單的，非遞歸來解決是有點難度的
快排也稱之為霍爾排序，因為發(fā)明者是霍爾，本來是命名為霍爾排序的，但是霍爾這個人對于自己創(chuàng)造的排序很自信，所以命名為快排
當然也是如他所料，快排確實很快，但是還沒有達到第一批次那個程度
快排gif
快排實現(xiàn)邏輯排序
單趟實現(xiàn)邏輯:
1.假設左邊為keyi，也就是對比數值
2，右邊R先走，循環(huán)尋找比keyi小的數值
3，左邊l走，循環(huán)尋找比keyi大的數值
4，交換找到的比keyi大的數值和小的數值，此時會導致小的在左邊，大的在右邊，最后相遇的時候交換keyi和相遇的元素多趟實現(xiàn):
1，多趟實現(xiàn)可以采取遞歸和非遞歸，但是總體邏輯都是一樣的，這里先講解一下遞歸的方式2，此時，我們會發(fā)現(xiàn)keyi下標所在位置，就是從前往后6，的位置，所以6回到自己的位置，我們以keyi為分界點進行切割【left,keyi-1】keyi【keyi+1,right】
進行遞歸，從而實現(xiàn)簡易版的速排
完善邏輯:
1，此時是快排還是有點問題的，當數值本身就是順序的時候
會發(fā)現(xiàn)此時的時間復雜度就變成了n^2，也就是不快了
2，原因是當本身就是排序好的時候，right右邊會一直往左邊尋
找，直到找到left，和自己交換，此時的時間復雜度也就是
n,n-1..1.0
3，解決辦法，我們可以三個數值取中，什么意思?也就是不管什么情況，我們都取出前三個數值，比如這里的
6 1 2
我們取出6 1 2，取出中間的位置，2，和keyi進行交換其他邏輯不變
完善邏輯:
1，此時我們發(fā)現(xiàn)邏輯沒有問題，但是速度還是和堆排序有點差距，那么此時我們繼續(xù)進行優(yōu)化
2，因為這里是用遞歸來實現(xiàn)的，我們發(fā)現(xiàn)，遞歸的實現(xiàn)是逐級實現(xiàn)的，也就是
第-層->第n層:1->2->3->4->…->n-1->n
這樣的遞歸方式來實現(xiàn)的，所以越到下面，遞歸的越多
我們可以把最后十層的遞歸用插入排序來實現(xiàn)一下，
3，為什么用插入排序?在排序里面有希爾排序，冒泡排序，選
擇排序，堆排序
希爾排序->插入排序的進階(書寫復雜)
冒泡排序->時間復雜度高
選擇排序->時間復雜度和冒泡一樣，比較高
堆排序->處理大型數字問題，這里沒必要
所以我們采取插入排序的方式進行解決
4，解決，我們只需要在遞歸的時候加一個判斷，就可以，當數
值小于等于10 的時候，我們直接調用插入排序解決問題。
此時速排(霍爾排序)，遞歸的方式也就結束了。圖解：
快排單趟實現(xiàn)
快排多趟實現(xiàn)
簡易版本的代碼實現(xiàn)
//霍爾方法(遞歸實現(xiàn)) void QuickSort01(int* a, int left, int right) {//遞歸停止條件if (left >= right)return;//單趟實現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動,是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動，是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實現(xiàn)//[left,keyi-1] keyi [keyi+1,right] 這里傳遞的是區(qū)間// 1 0 1 2 1 當只剩一個數值的時候，也就是這個區(qū)間的時候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right); }解釋：
函數定義：
QuickSort01函數接受一個整數數組的指針a以及兩個整數left和right，分別表示要排序的數組部分的起始和結束索引。遞歸終止條件：如果
left大于或等于right，則當前子數組無需排序，遞歸結束。初始化：設置兩個指針
begin和end分別指向子數組的起始和結束位置，keyi作為基準元素的索引，初始位置設為left。單趟排序：
- 使用兩個內層循環(huán)，一個從右側向左尋找比基準值小的元素，另一個從左側向右尋找比基準值大的元素。
- 當找到合適的元素時，交換這兩個元素的位置，然后繼續(xù)尋找，直到
begin和end相遇。基準值定位：將基準值
a[keyi]與begin指向的元素交換，此時begin指向的位置是基準值的最終位置。遞歸排序：對基準值左邊的子數組
[left, keyi - 1]和右邊的子數組[keyi + 1, right]遞歸調用QuickSort01函數進行排序。效率：快速排序的平均時間復雜度為O(n log n)，但在最壞情況下（如數組已經排序）時間復雜度會退化到O(n^2)。霍爾方法通過減少不必要的數據交換來提高排序效率。
輔助函數：
Swap函數用于交換兩個元素的值，雖然在代碼中未給出定義，但它是快速排序中交換元素的關鍵操作。快速排序算法的效率和性能在實際應用中通常優(yōu)于其他O(n log n)算法，如歸并排序，尤其是在數據量較大時。然而，其穩(wěn)定性不如歸并排序，且在最壞情況下性能較差。在實際應用中，快速排序通常與其他排序算法結合使用，以提高整體排序性能。
注意事項
注意事項1
這里有一個關鍵點是很重要的，也就是我們是從右邊先出發(fā)的，因為我們的keyi的位置在左邊。
如果我們的keyi的下標在左邊，并且左邊先走的話，就會產生一種結果
如圖
注意事項2
不是等于就交換，是等于會跳過往下找
當我們寫的是不等于的時候
快排完整代碼實現(xiàn)-（三數值取中）
此時存在的最大問題就是如果排序本身就是順序排序的情況下，這時間復雜度反而高了，所以我們對排序進行修改
//交換函數 void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp; } //霍爾方法(遞歸實現(xiàn)) //三數取中 int GetMid(int* a, int left, int right) {//三數取中傳參的是下標，我們取中也是根據下標進行計算的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;//三數取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動,是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動，是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實現(xiàn)//[left,keyi-1] keyi [keyi+1,right] 這里傳遞的是區(qū)間// 1 0 1 2 1 當只剩一個數值的時候，也就是這個區(qū)間的時候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right); }總結：
函數目的：選擇一個合適的基準值，以提高快速排序算法的效率。
傳入參數：接受一個整數數組的指針
a，以及表示數組部分邊界的整數left和right。計算中間索引：通過
(left + right) / 2計算中間元素的索引mid。三數取中邏輯：
- 如果數組的第一個元素
a[left]小于最后一個元素a[right]：
- 如果中間元素
a[mid]小于第一個元素，則選擇第一個元素作為基準。- 如果中間元素大于最后一個元素，則選擇最后一個元素作為基準。
- 否則，選擇中間元素作為基準。
- 如果第一個元素大于或等于最后一個元素（即數組首尾元素已經排序或相等）：
- 如果中間元素大于第一個元素，則選擇第一個元素作為基準。
- 如果中間元素小于最后一個元素，則選擇最后一個元素作為基準。
- 否則，選擇中間元素作為基準。
返回值：函數返回基準值的索引。
優(yōu)化目的：通過三數取中法選擇基準，可以減少快速排序在特定情況下性能退化的問題，如數組已經排序或包含大量重復元素。
適用場景：適用于快速排序算法中，作為選擇基準值的策略。
性能影響：選擇一個好的基準值可以確保數組被均勻地劃分，從而接近快速排序的最佳平均時間復雜度O(n log n)。
三數取中法是一種簡單而有效的基準選擇策略，它通過比較數組的首元素、尾元素和中間元素，來確定一個相對平衡的基準值，有助于提高快速排序的整體性能和穩(wěn)定性。
快排完整代碼實現(xiàn)-（減少遞歸次數）
此時我們還面臨的問題就是底層的遞歸次數過多的問題，遞歸會隨著次數的增加呈現(xiàn)倍數增長，就像三角形一樣
最后我們減少遞歸次數，把最底層從遞歸改為插入排序，邏輯完成
快排完整代碼
//交換函數 void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp; } //霍爾方法(遞歸實現(xiàn)) //三數取中 int GetMid(int* a, int left, int right) {//三數取中傳參的是下標，我們取中也是根據下標進行計算的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;//當區(qū)間數值小于10個，此時我們直接采取插入排序進行排序if (right - left + 1 <= 10){//這里記得是左右區(qū)間，所以不能只傳遞a，而是傳遞a + leftInsertionSort(a + left, right - left + 1);}else{//三數取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動,是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動，是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//多趟遞歸實現(xiàn)//[left,keyi-1] keyi [keyi+1,right] 這里傳遞的是區(qū)間// 1 0 1 2 1 當只剩一個數值的時候，也就是這個區(qū)間的時候，遞歸停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi + 1, right);} }代碼解釋：
三數取中函數
GetMid:
- 計算中間索引?
mid。- 通過比較數組的首元素、尾元素和中間元素，選擇一個合適的基準值。
- 如果首元素小于尾元素，選擇中間元素和首尾元素中較小或較大的一個作為基準。
- 如果首元素大于尾元素，選擇中間元素和首尾元素中較大或較小的一個作為基準。
快速排序函數
QuickSort01:
- 遞歸停止條件：如果當前區(qū)間的左右索引?
left?和?right?交叉或重合，則不需要排序。- 當區(qū)間大小小于或等于10時，使用插入排序，因為小數組上插入排序更高效。
- 使用?
GetMid?函數獲取基準值的索引，并將基準值與首元素交換。- 霍爾方法的分區(qū)操作，通過兩個指針?
begin?和?end?進行分區(qū)。- 遞歸地對基準值左邊和右邊的子區(qū)間進行快速排序。
輔助函數
Swap:
- 交換兩個元素的值，雖然代碼中未給出定義，但通常是一個簡單的值交換操作。
總結：
- 算法優(yōu)化: 通過三數取中法選擇基準值，可以提高基準值的選中質量，從而提高快速排序的效率。
- 小數組優(yōu)化: 當子數組的大小，小于或等于10時，使用插入排序代替快速排序，因為小數組上插入排序的性能通常更好。
- 遞歸與迭代: 快速排序是一個遞歸算法，但在小數組上切換到迭代的插入排序可以減少遞歸開銷。
- 分區(qū)策略: 使用霍爾方法進行分區(qū)，這是一種高效的分區(qū)策略，可以減少不必要的數據交換。
- 適用場景: 這種改進的快速排序適用于大多數需要排序的場景，尤其是在大數據集上，它能夠保持較好的性能。
- 時間復雜度: 平均情況下時間復雜度為 O(n log n)，最壞情況下（已排序數組）時間復雜度為 O(n^2)，但由于三數取中法和插入排序的結合，最壞情況出現(xiàn)的概率降低。
通過這種改進，快速排序算法在處理小數組時更加高效，同時在大數據集上也能保持較好的性能，使其成為一種更加健壯的排序算法。
快排的時間復雜度
快速排序算法的時間復雜度取決于分區(qū)過程中基準值的選擇。
理想情況下
基準值會將數組均勻地分成兩部分，每部分的元素數量大致相等。對于這種理想情況，快速排序的時間復雜度是 O(n log n)，其中 n 是數組中的元素數量。
最壞情況下
如果基準值的選擇非常不均勻，從而導致每次分區(qū)都極不平衡，快速排序的最壞時間復雜度會退化到 O(n^2)。這種情況通常發(fā)生在數組已經排序或所有元素相等的情況下。
在當前代碼中
使用了三數取中法來選擇基準值，這種方法可以在大多數情況下避免選擇極端值作為基準，從而減少最壞情況發(fā)生的概率。但是，如果數組的元素分布非常不均勻，或者存在大量重復元素，仍然可能遇到性能退化的情況。
此外，代碼中還引入了一個優(yōu)化：當子數組的大小小于或等于10時，使用插入排序而不是快速排序。這是因為對于小數組，插入排序的性能通常比快速排序更好，而且插入排序是穩(wěn)定的。這個優(yōu)化可以提高算法在處理小數組時的效率。
總的來說，這個改進的快速排序算法的平均時間復雜度是 O(n log n)，但在最壞情況下仍然是 O(n^2)。然而，由于三數取中法和插入排序的優(yōu)化，最壞情況的發(fā)生概率被大大降低了。在實際應用中，這種改進的快速排序算法通常能夠提供非常高效的排序性能。
前后修改之后速度進行對比
優(yōu)化，和不優(yōu)化之間的區(qū)別
這里計算的是一千萬個數值進行排序的毫秒數值，也就是不到一秒，還是很快的，尤其是修改之后，解決了大量的遞歸問題
注意事項
這里調用的插入排序是升序，寫的快排也是升序，如果你需要測試降序，那么你需要把插入排序一起改成降序，不然會導致排序沖突
快排（前后指針-遞歸解決）
前言
快排解決辦法有很多種，這里我再拿出來一種前后指針版本
雖然這個版本的時間復雜度和霍爾一樣，邏輯也差不多，但是實際排序過程，確實會比霍爾慢一點
快排gif
快排前后指針實現(xiàn)邏輯：
前后指針實現(xiàn)邏輯(升序):
單趟排序:
1，我們使用遞歸來進行實現(xiàn)，所以我們先實現(xiàn)單趟排序
2，定義兩個下標，也就是所謂的指針，初始的時候，一個指向最左邊第一個元素(prev)，一個指向第二個元素(cur)，最后定義一個對比keyi3，此時先判斷我們的cur是不是小于keyi。cur小于keyi的話:prev++，交換，之后cur++4，但是我們如果和自己交換此時沒有什么意義，所以這里我們需要做一個處理
5，繼續(xù)往前走，如果遇見的是:比keyi下標大的元素此時，cur++，直到遇見的是比keyi下標小的元素，循環(huán)執(zhí)行.prev++，交換，之后cur++6，最后cur走到最后一個元素，我們交換keyi的下標元素和prev的下標元素
多趟實現(xiàn):
1，遞歸進行分割:【left，keyi-1】keyi【keyi+1，right】
2，停止條件就是當left>=right
原因:【left, keyi-1】keyi【keyi+1, right】
快排單趟實現(xiàn)
這里只是圖解單趟實現(xiàn)邏輯，因為多趟實現(xiàn)的邏輯和霍爾的一樣，也是遞歸，所以不進行多次書寫
代碼實現(xiàn)
這里的代碼實現(xiàn)的核心邏輯不一樣，大的框架是一樣的，也就是三數取中，以及減少遞歸從而使用插入排序這樣的邏輯是一樣的，下面我們來看看這個新的組裝怪
//快排（前后指針方法）(遞歸實現(xiàn)) void QuickSort02(int* a, int left, int right) {//遞歸停止條件if (left >= right)return;//創(chuàng)建兩個變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當快指針到尾的時候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數值，所以遇見大的++，小的停止if (a[keyi] > a[cur]){//停止之后，慢指針++,并且進行交換,因為中間才是大的數值，cur遇見大數值++。遇見小數值才停下來prev++;Swap(&a[prev], &a[cur]);//同理快指針也進行++，往后移動cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;//多趟遞歸實現(xiàn)//[left,keyi-1] keyi [keyi+1,right] 這里傳遞的是區(qū)間// 1 0 1 2 1 當只剩一個數值的時候，也就是這個區(qū)間的時候，遞歸停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi + 1, right); }總結：
算法基礎：快速排序是一種分而治之的排序算法，它通過遞歸地將數組分為較小的子數組，然后對這些子數組進行排序。
分區(qū)策略：使用前后指針（
prev和cur）進行分區(qū)，而不是傳統(tǒng)的左右指針。這種方法在某些情況下可以減少元素交換的次數。基準值選擇：基準值（
keyi）是數組的第一個元素，即left索引對應的元素。指針移動規(guī)則：
prev作為慢指針，用于跟蹤比基準值小的元素的邊界。cur作為快指針，從left + 1開始遍歷數組。元素交換：當快指針指向的元素大于基準值時，不進行交換，快指針繼續(xù)移動；當快指針指向的元素小于或等于基準值時，與慢指針所指元素交換，然后慢指針和快指針都向前移動。
遞歸排序：在基準值確定之后，遞歸地對基準值左邊和右邊的子數組進行排序。
時間復雜度：平均情況下，快速排序的時間復雜度為O(n log n)。最壞情況下，如果每次分區(qū)都極不平衡，時間復雜度會退化到O(n^2)。
空間復雜度：由于遞歸性質，快速排序的空間復雜度為O(log n)。
算法優(yōu)化：通過前后指針方法，可以在某些情況下提高快速排序的性能，特別是當基準值接近數組中間值時。
適用場景：快速排序適用于大多數需要排序的場景，特別是在大數據集上，它通常能夠提供非常高效的排序性能。
優(yōu)化
這里我們可以看到，cur無論是if還是else里面都需要++，所以我們直接放到外面
其次我們?yōu)榱诵?#xff0c;不和自己交換，我們不和自己交換，進行一個判斷條件
快慢指針代碼優(yōu)化（完整）
//交換函數 void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp; } //快排（前后指針方法）(遞歸實現(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{//三數取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實現(xiàn)//創(chuàng)建兩個變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當快指針到尾的時候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數值，所以遇見大的++，小的停止if (a[keyi] > a[cur] && prev++ != cur){//停止之后，慢指針++,并且進行交換,因為中間才是大的數值，cur遇見大數值++。遇見小數值才停下來Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;//多趟遞歸實現(xiàn)//[left,keyi-1] keyi [keyi+1,right] 這里傳遞的是區(qū)間// 1 0 1 2 1 當只剩一個數值的時候，也就是這個區(qū)間的時候，遞歸停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi + 1, right);} }總結：
基本遞歸結構：算法使用遞歸調用來處理子數組，這是快速排序算法的核心結構。
小數組優(yōu)化：當子數組的大小小于或等于10時，算法使用插入排序而不是快速排序，因為插入排序在小規(guī)模數據上更高效。
三數取中法：為了更均勻地分割數組，算法使用三數取中法選擇基準值，這有助于減少最壞情況發(fā)生的概率。
前后指針方法：算法使用兩個指針（
prev和cur），其中prev作為慢指針，cur作為快指針，通過這種方式進行一次遍歷完成分區(qū)。分區(qū)操作：快指針從
left + 1開始遍歷，如果當前元素小于基準值，則與慢指針所指的元素交換，然后慢指針向前移動。遞歸排序子數組：基準值確定后，算法遞歸地對基準值左邊和右邊的子數組進行排序。
時間復雜度：平均情況下，算法的時間復雜度為O(n log n)，最壞情況下為O(n^2)。但由于采用了小數組優(yōu)化和三數取中法，最壞情況的發(fā)生概率降低。
空間復雜度：算法的空間復雜度為O(log n)，這主要由于遞歸調用導致的?？臻g使用。
適用場景：這種改進的快速排序算法適用于大多數需要排序的場景，尤其是在大數據集上，它能夠提供非常高效的排序性能，同時在小數據集上也表現(xiàn)出較好的效率。
算法穩(wěn)定性：由于使用了插入排序對小規(guī)模子數組進行排序，算法在處理小規(guī)模數據時具有穩(wěn)定性。
注意：在實際測試·里面，前后指針比霍爾排序慢一點
通過這種混合排序策略，算法在保持快速排序優(yōu)點的同時，也提高了在特定情況下的排序效率，使其成為一種更加健壯的排序方法。
注意事項
這里調用的插入排序是升序，寫的快排也是升序，如果你需要測試降序，那么你需要把插入排序一起改成降序，不然會導致排序沖突
快排（霍爾版本-非遞歸解決）
前言
快拍不僅需要學習遞歸，還需要學東西非遞歸，這樣更有助于我們理解快拍
首先我們需要知道，非遞歸的學習需要使用棧，所以如果我們的棧的學習是不完善的，建議學習一下棧
非遞歸gif
這里其實單詞循環(huán)是誰其實不重要，可以是前后指針，也可以是霍爾方式，這里我們拿出來霍爾的gif來觀看
實現(xiàn)圖解
非遞歸實現(xiàn)主要是依賴棧來進行實現(xiàn)，依賴棧的特點，先進后出，后進前出
1，首先我們需要寫一個棧的庫進行調用
2，入區(qū)間，調用單次排序的實現(xiàn)思路
3，入區(qū)間的時候，我們需要把握入棧和出棧的關鍵
代碼實現(xiàn)（前后指針）
首先我們調用棧
頭文件
#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，等同于下標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); // 獲取棧中有效元素個數 int StackSize(Stack* ps); // 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 int StackEmpty(Stack* ps);實現(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) {//判斷需不需要擴容,相等的時候需要擴容if (ps->_capacity == ps->_top){//判斷空間是不是0，因為為0的時候，再多的數值*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 因為我們這里等同size，也就是個數，等于0都不行assert(ps);return ps->_a[ps->_top - 1]; } // 獲取棧尾元素 STDataType Stackhop(Stack* ps) {assert(ps && ps->_top > 0);return ps->_a[0]; } // 獲取棧中有效元素個數 int StackSize(Stack* ps) {//獲取有效元素的時候，里面可以沒有元素assert(ps);return ps->_top; } // 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 int StackEmpty(Stack* ps) {//這里的判斷是不是空，也就是里面是不是有數值，這里等于是一個判斷，沒有的話返回ture，有的話返回falseassert(ps);return ps->_top == 0; }其次調用前后指針來實現(xiàn)
//快排（前后指針方法）(單趟) int one_QuickSort02(int* a, int left, int right) {//三數取中//int mid = GetMid(a, left, right);//Swap(&a[mid], &a[left]);//單趟實現(xiàn)//創(chuàng)建兩個變量，作為前后指針使用int prev = left; int cur = prev + 1;int keyi = left;//當快指針到尾的時候，跳出循環(huán)->交換while (cur <= right){//前后指針中間是比a[keyi]大的數值，所以遇見大的++，小的停止if (a[keyi] > a[cur] && prev++ != cur){//停止之后，慢指針++,并且進行交換,因為中間才是大的數值，cur遇見大數值++。遇見小數值才停下來Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[keyi], &a[prev]);return prev; //快排 非遞歸實現(xiàn) void QuickSort003(int* a, int left, int right) {//非遞歸實現(xiàn)主要是用棧來模擬實現(xiàn)，在c++里面我們可以直接調用棧，但是在C語言里面我們只能寫出來棧再進行調用//思路（霍爾方式）//1單趟的思路還是一樣的，如果是升序的情況下，依舊是先從右邊出發(fā)（找小），后從左邊出發(fā)（找大）//2,循環(huán)遞歸過程我們改為利用進棧出棧來實現(xiàn)。首先我們需要明確這里傳遞的是區(qū)間，也就是利用棧實現(xiàn)的時候，我們傳遞的是數組和區(qū)間，利用區(qū)間進行計算。這里的關鍵在于傳遞區(qū)間的時候，我們需要詳細知曉棧的特點，先進后出，后進后出，。所以在傳遞區(qū)間的時候，如果多趟循環(huán)，一分為二的時候，我們需要先傳遞右側的區(qū)間，再傳遞左側區(qū)間，因為我們需要先計算左側。同理進去之后，我們需要繼續(xù)入棧，需要先-入計算左側的區(qū)間的右側區(qū)間，后入左側區(qū)間。這樣就會先計算左側區(qū)間。棧的特性，先進后出，后進先出// // 所以這里我們把霍爾排序單趟實現(xiàn)來單獨拿出來，這樣的話我們接受的返回值是中間值//[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);//假設入棧區(qū)間此時來到-> 0-2int mini = one_QuickSort02(a, begin, end);//經過計算之后，此時中間值是，keyi=1//0 1 2 三個區(qū)間三個數值，此時進行入棧判斷//[begin,keyi-1]keyi[keyi+1,end]//[ 0 , 0 ] 1 [ 2 , 2 ]//所以不繼續(xù)入棧if (mini + 1 < end){//右邊先入棧，后計算StackPush(&ps, end);StackPush(&ps, mini + 1);}if (mini - 1 > begin){//左邊區(qū)間后入棧，先計算StackPush(&ps, mini - 1);StackPush(&ps, begin);}}StackDestroy(&ps); }解釋：
one_QuickSort02?函數這個函數是快速排序算法中的單趟排序實現(xiàn)。它使用前后指針法來實現(xiàn)，具體步驟如下：
- 初始化指針：
prev?初始化為?left，cur?初始化為?prev + 1，keyi?也初始化為?left。- 循環(huán)：當?
cur?小于等于?right?時，執(zhí)行循環(huán)體內的操作。- 比較和交換：如果當前?
cur?指向的元素小于?keyi?指向的元素，并且?prev?指針不等于?cur，說明找到了一個比基準值小的元素，需要交換。將?a[prev]?和?a[cur]?交換，并將?prev?指針向前移動一位。- 移動快指針：無論是否發(fā)生交換，
cur?指針都向前移動一位。- 交換基準值：循環(huán)結束后，將?
keyi?指向的元素與?prev?指向的元素交換，此時?prev?指向的是比基準值小的元素的最后一個位置。- 返回值：函數返回?
prev?的值，這個值是下一次分區(qū)的起始位置。
QuickSort003?函數這個函數是快速排序的非遞歸實現(xiàn)，使用棧來模擬遞歸過程。具體步驟如下：
- 初始化棧：創(chuàng)建并初始化一個棧?
ps。- 入棧：將?
left?和?right?作為初始區(qū)間入棧。- 循環(huán)：只要棧不為空，就執(zhí)行循環(huán)。
- 單趟排序：每次從棧中取出兩個值作為區(qū)間的左右邊界，調用?
one_QuickSort02?函數進行單趟排序，得到中間值?mini。- 判斷區(qū)間：根據?
mini?的位置，判斷是否需要繼續(xù)對左右區(qū)間進行排序。
- 如果?
mini + 1 < end，則說明右側還有元素需要排序，將?end?和?mini + 1?入棧。- 如果?
mini - 1 > begin，則說明左側還有元素需要排序，將?begin?和?mini - 1?入棧。- 出棧：每次循環(huán)結束，都會從棧中彈出兩個值，直到棧為空。
- 銷毀棧：循環(huán)結束后，銷毀棧。
對于棧和隊列不是很明白的，推薦看一下棧和隊列篇章
數據結構-棧和隊列(速通版本)-CSDN博客
代碼實現(xiàn)（霍爾排序）
這里其實不管是前后指針，還是霍爾排序，其實都是一樣的，因為本質上都是讓數值到應該到的位置，所以本質上是一樣的，這里我再調用一個霍爾的方式是因為一方面和前后指針的調用形成對比，一方面有不同的注釋
//交換函數 void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp; } //霍爾方法(單趟實現(xiàn)) int one_QuickSort01(int* a, int left, int right) {//三數取中int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);//單趟實現(xiàn)//右邊找小，左邊找大int begin = left; int end = right;int keyi = begin;while (begin < end){//右邊找小，不是的話移動,是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] <= a[end]){end--;}//左邊找大，不是的話移動，是的話不移動，并且跳出循環(huán)while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin; } //霍爾方法再次調用 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);//計算區(qū)間//假設傳遞的區(qū)間是2-4 --->>> 傳遞過來的數值也就是下標是（1）4-2=2/2=1 --->>>此時mini=2,也就是此時我們返回的數值要么是第一個數值，要么的第二個數值的下標，不管是哪個，此時都會變成一個數值//此時我們繼續(xù)入棧，入棧的是mini+1 也就是3-4，繼續(xù)傳遞區(qū)間，此時傳遞回來的mini還是3，但是此時3+4==4了 所以不繼續(xù)入棧，因為數值只有一個，不是區(qū)間了//右區(qū)間入棧，后出if (mini + 1 < end){//入右邊，之后左邊，這樣取的時候棧頂先取左邊，之后右邊StackPush(&ps, end);StackPush(&ps, mini + 1);}//左區(qū)間入棧，先出if (mini - 1 > begin){StackPush(&ps, mini - 1);StackPush(&ps, begin);}}StackDestroy(&ps); }解釋：
one_QuickSort01?函數這個函數是霍爾快速排序算法的單趟實現(xiàn)，具體步驟如下：
- 三數取中：使用?
GetMid?函數找到數組?a?中間位置的元素，并將其與數組第一個元素交換（left?索引位置的元素）。- 初始化指針：
begin?初始化為?left，end?初始化為?right，keyi?初始化為?begin。- 循環(huán)：使用?
while?循環(huán)，只要?begin?小于?end，就繼續(xù)執(zhí)行循環(huán)。- 右邊找小：從?
end?向?begin?掃描，找到第一個小于基準值?a[keyi]?的元素。如果找到，end?指針向前移動，否則跳出循環(huán)。- 左邊找大：從?
begin?向?end?掃描，找到第一個大于基準值?a[keyi]?的元素。如果找到，begin?指針向后移動，否則跳出循環(huán)。- 交換元素：將找到的兩個元素?
a[begin]?和?a[end]?交換位置。- 基準值交換：循環(huán)結束后，將?
keyi?指向的元素與?begin?指向的元素交換，此時?begin?指向的是基準值的正確位置。- 返回值：函數返回?
begin?的值，這個值是下一次分區(qū)的起始位置。
QuickSort03?函數這個函數是快速排序的非遞歸實現(xiàn)，使用棧來模擬遞歸過程：
- 初始化棧：創(chuàng)建并初始化一個棧?
ps。- 入棧：將初始區(qū)間的左右邊界?
left?和?right?入棧。- 循環(huán)：只要棧不為空，就繼續(xù)執(zhí)行循環(huán)。
- 單趟排序：每次從棧中取出兩個值作為區(qū)間的左右邊界，調用?
one_QuickSort01?函數進行單趟排序，得到中間值?mini。- 計算新區(qū)間：根據?
mini?的位置，計算新的左右區(qū)間。
- 如果?
mini + 1 < end，則說明右側還有元素需要排序，將?end?和?mini + 1?入棧。- 如果?
mini - 1 > begin，則說明左側還有元素需要排序，將?begin?和?mini - 1?入棧。- 棧的特性：由于棧是后進先出（LIFO）的數據結構，所以先入棧的是右側區(qū)間，后入棧的是左側區(qū)間，這樣在出棧時，會先處理左側區(qū)間，再處理右側區(qū)間。
- 銷毀棧：循環(huán)結束后，銷毀棧。
這種非遞歸實現(xiàn)的快速排序算法利用了棧的特性來避免遞歸調用，從而減少了函數調用的開銷，并且在處理大數據集時，可以避免遞歸深度過大導致的棧溢出問題。
歸并排序?（遞歸實現(xiàn)）
前言
歸并排序是一種邏輯很簡單，但是實現(xiàn)有點難度的排序，尤其是非遞歸，對于區(qū)間的把握更是需要一點邏輯的推導，但是沒有關系，輕松拿捏
歸并排序gif
歸并排序單趟實現(xiàn)
1，創(chuàng)建tmp數組，
2，遞歸到最小值進行排序，同時拷貝到題目破數組里面
3，這里的關鍵邏輯實現(xiàn)是，遞歸回來的時候進行排序
4，最后我們把數值重新拷貝回去原數組
注意：這里的取值我們直接取中間值進行遞歸，一分為二
代碼實現(xiàn)注意事項
關于創(chuàng)建tmp數組，我們需要創(chuàng)建的數組應該是等大的，要么就進行初始化。
- 因為我們是malloc出來的空間，
- 為什么malloc出來的空間必須是等大的，因為這里我們用的是Visual Studio 2022的編譯器，這個編譯器里面是不支持可變長數組的。所以我們需要用malloc，或者realloc來實現(xiàn)創(chuàng)建空間，也就是動態(tài)內存的分配
- malloc創(chuàng)建空間的時候，空間里面是有隨機值的
- realloc創(chuàng)建的空間里面的數值是0
- 所以一旦我們進行排序的時候，如果我們不進行覆蓋的話，這里面的數值也會參與排序，從而導致數值出現(xiàn)偏差
這里對于這一點不清楚的可以看看之前寫的文章，因為當時寫這個文章的時候，剛接觸編程，所以講述的主要是以語法和一些簡單的性質特點，希望可以起到幫助
- 動態(tài)內存函數的使用和綜合實踐-malloc，free，realloc，calloc_內存申請函數-CSDN博客
代碼實現(xiàn)
//歸并排序（遞歸實現(xiàn)）子函數(實現(xiàn)函數) void _MergeSort01(int* a, int* tmp, int begin, int end) {if (begin >= end)return;int mini = (begin + end) / 2;//注意，這里關鍵在于，區(qū)間的傳遞，//不應該傳遞【left,mini-1】【mini,right】// 應該傳遞【left,mini】【mini+1,right】//遞歸左右區(qū)間, 遞歸到最小個數進行對比_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++];}//數據從tmp拷貝回去數組a里面memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //歸并排序（遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort01(int* a, int n) {//這里n傳遞過來的是個數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; }解釋：
_MergeSort01 函數：這是歸并排序的遞歸子函數，它接收三個參數：數組
a，臨時數組tmp，以及要排序的數組區(qū)間[begin, end]。
- 如果?
begin?大于或等于?end，則表示區(qū)間內沒有元素或只有一個元素，不需要排序，直接返回。- 計算區(qū)間的中點?
mini，將數組分為兩部分：[begin, mini]?和?[mini + 1, end]。- 對這兩部分分別遞歸調用?
_MergeSort01?函數進行排序，直到每個子區(qū)間只有一個元素。合并過程：
- 初始化兩個指針?
begin1?和?end1?指向第一個子區(qū)間的開始和結束位置，begin2?和?end2?指向第二個子區(qū)間的開始和結束位置。- 使用一個索引?
i?指向?tmp?數組的當前位置，用于存放合并后的有序元素。- 使用兩個?
while?循環(huán)來比較兩個子區(qū)間的元素，將較小的元素復制到?tmp?數組中，并移動對應的指針。- 如果第一個子區(qū)間的所有元素已經被復制到?
tmp?中，但第二個子區(qū)間還有剩余元素，將這些剩余元素復制到?tmp?數組的剩余位置。- 同理，如果第二個子區(qū)間的所有元素已經被復制，將第一個子區(qū)間的剩余元素復制到?
tmp。拷貝回原數組：
- 使用?
memcpy?函數將?tmp?數組中從索引?begin?開始的元素復制回原數組?a。這里計算了需要復制的元素數量為?end - begin + 1，乘以?sizeof(int)?來確定字節(jié)數。MergeSort01 函數：這是歸并排序的初始化函數，接收數組
a和數組的長度n。
- 首先，使用?
malloc?分配一個臨時數組?tmp，大小為?n?個?int。- 如果內存分配失敗，使用?
perror?打印錯誤信息，并調用?exit(1)?退出程序。- 調用?
_MergeSort01?函數，傳入數組?a、臨時數組?tmp?和整個數組的區(qū)間?[0, n - 1]?進行排序。- 排序完成后，使用?
free?釋放?tmp?所占用的內存，并設置?tmp?為?NULL。歸并排序的時間復雜度為 O(n log n)，在大多數情況下表現(xiàn)良好，尤其是當數據量大且需要穩(wěn)定排序時。不過，由于它需要額外的內存空間（如這里的
tmp數組），在內存受限的情況下可能不是最佳選擇。
遞歸排序（非遞歸解決）
前言
這里遞歸排序的非遞歸方式還是比較有難度的，所以需要多次觀看兩遍，我也會多次詳細的講解，促進知識的理解
非遞歸實現(xiàn)gif
非遞歸實現(xiàn)單趟實現(xià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ū)間越界的，我們直接下一次進行遞歸就可以
?? ??? ??? ?//end2，我們重新設定新的end2的區(qū)間所以我們需要對這個區(qū)間進行解決
代碼的逐步實現(xiàn)
這里代碼的實現(xiàn)，因為非遞歸實現(xiàn)是有難度的，所以這里我不會直接給出答案，而是逐步的寫出步驟，促進理解
1，創(chuàng)建拷貝空間tmp，設定gap，一組假設初始1個數值，當然初始的時候，實際也是一個數值
//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1; }2，區(qū)間的設定
這里依舊是兩個區(qū)間，我們根據這個區(qū)間設定的數值
這里是很關鍵的一點
?? ?int begin1 = 0, end1 = 0 + gap - 1;
?? ?int begin2 = 0 + gap, end2 = 0 + 2 * gap - 1;//假設此時就兩個數值，一組是一個數值，也就是這兩個數值進行最小對比
//begin1左區(qū)間的初始位置，肯定是0
//end1左區(qū)間的結束位置。
- 也就是第一個區(qū)間的結束位置，也就是一組，
- -1是因為一組是實際的個數
- +0，這里因為加的是第一個區(qū)間起始位置
- 因為我們也可能是2-4區(qū)間的，不可能只是這一個區(qū)間
//begin2第二個區(qū)間的起始位置，這里還是比較好理解的，只要理解了end1
//end2第二個區(qū)間的結束位置，這里同理，
- 我們有可能是2-4區(qū)間的，不只是0-1或者0-2區(qū)間的。而且隨著第一次排序的結束，第二次排序就變成兩個合并了，繼續(xù)和另外的對比，所以是變化的
- 0也就是初始位置
- 2*gap，因為這里是需要加上中間兩組，
- 最后-1，因為gap是個數，不是下標
//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1;int begin1 = 0, end1 = 0 + gap - 1;int begin2 = 0 + gap, end2 = 0 + 2 * gap - 1; }3，排序的實現(xiàn)
//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1;while (gap < 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ū)間，并且我們需要一邊拷貝一邊拷貝回去，為什么需要一邊排序一邊拷貝回去，在接下來的越界行為里面我們會進行講解
最后需要關注的點是，關于拷貝空間的大小，一定是end2-begin1，因為這兩個區(qū)間是排序成功然后進入到tmp里面
所以我們需要從tmp拷貝回去，不能弄錯了
//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1;while (gap < 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數組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;} }5，解決越界行為
這里我們可以很清楚的看到哪些位置會產生越界行為
這里我們處理一下之后，我們發(fā)現(xià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ū)間越界的，我們直接下一次進行遞歸就可以
?? ??? ??? ?//end2，我們重新設定新的end2的區(qū)間//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1;while (gap < 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;//但是此時可能產生越界行為,我們可以打印出來看一下//產生越界的//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ū)間越界的，我們直接下一次進行遞歸就可以//end2，我們重新設定新的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，因為end2是下標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數組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;} }
時間復雜度
時間復雜度分析如下：
分解階段：歸并排序首先將原始數組分解成多個子數組，每個子數組的大小為1。這個過程是線性的，時間復雜度為 O(n)，其中 n 是原始數組的大小。
合并階段：在合并階段，算法將這些有序的子數組逐步合并成更大的有序數組。每次合并操作都需要將兩個有序數組合并成一個更大的有序數組，這個過程的時間復雜度是 O(n)。
重復合并：歸并排序的合并階段會重復進行，直到所有的元素都被合并成一個有序數組。合并的次數可以看作是對數級的，具體來說，是 log2(n) 次。
綜合以上兩點，歸并排序的總時間復雜度主要由合并階段決定，因為分解階段是線性的，而合并階段雖然每次都是線性的，但由于重復了對數級次數，所以總的時間復雜度是：
𝑂(𝑛)+𝑂(𝑛log?𝑛)
由于在大 O 符號中，我們只關注最高次項和系數，所以歸并排序的時間復雜度通常被簡化為：𝑂(𝑛log?𝑛)
這意味著歸并排序的時間效率與數組的大小成對數關系，是相當高效的排序算法。此外，歸并排序是一種穩(wěn)定的排序算法，它保持了相等元素的原始順序。然而，它需要與原始數組同樣大小的額外空間來存儲臨時數組，這可能會在空間受限的情況下成為一個問題。
代碼實現(xiàn)
//歸并排序（非遞歸實現(xiàn)）（創(chuàng)建tmp函數） void MergeSort02(int* a, int n) {//這里n傳遞過來的是個數int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSort01:tmp:err:");exit(1);//正常退出}//假設初始化起始是一組int gap = 1;while (gap < 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;//但是此時可能產生越界行為,我們可以打印出來看一下//產生越界的//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ū)間越界的，我們直接下一次進行遞歸就可以//end2，我們重新設定新的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，因為end2是下標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數組里面,這里的區(qū)間是end2-begin1之間的區(qū)間memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;} }解釋：
內存分配：首先，函數使用
malloc分配一個與原數組a同樣大小的臨時數組tmp。如果內存分配失敗，使用perror打印錯誤信息，并調用exit退出程序。初始化間隔：
gap變量初始化為 1，表示每個元素自身作為一個有序的子數組。外層循環(huán)：使用
while循環(huán)來逐步增加gap的值，每次迭代將gap乘以 2。這個循環(huán)繼續(xù)進行，直到gap大于或等于數組的長度n。內層循環(huán)：對于每個
gap值，使用for循環(huán)遍歷數組，計算每次合并操作的起始索引i。每次迭代，i增加gap * 2，以確保每次處理的子數組間隔是gap。計算子數組邊界：在每次迭代中，計算兩個子數組的起始和結束索引：
begin1、end1和begin2、end2。這兩個子數組的間隔是gap。處理數組越界：如果
begin2大于數組長度n，循環(huán)將終止。如果end2超出了數組的界限，將其調整為n-1。合并子數組：使用
while循環(huán)來合并兩個子數組。比較a[begin1]和a[begin2]，將較小的元素復制到tmp數組中，并相應地移動索引。當一個子數組的所有元素都被復制后，使用另外兩個while循環(huán)復制剩余子數組中的元素。拷貝回原數組：使用
memcpy將tmp中的有序子數組復制回原數組a。這里，拷貝的區(qū)間是從索引i到end2，拷貝的元素數量是end2 - i + 1。更新間隔：外層循環(huán)的
gap每次迭代后翻倍，這樣在每次迭代中，處理的子數組的大小逐漸增加，直到整個數組被排序。非遞歸的歸并排序在某些情況下可能比遞歸版本更有效，因為它避免了遞歸調用的開銷，尤其是在深度很大的遞歸樹中。然而，它需要更多的迭代來逐步構建有序數組，因此在實際應用中，選擇哪種實現(xiàn)取決于具體的需求和場景。
計數排序
前言
計數排序是速度特別快的一種排序方式，甚至說可以達到o（n），什么概念，一趟就可以實現(xiàn)，這是很快的，雖然具備一定的局限性，但是這個速度也是嘆為觀止的
計數排序gif
實現(xiàn)圖解
這里的核心邏輯就在于，我們需要入數組和出數組這兩點
代碼實現(xiàn)
//計數排序 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];}}//計算差值,需要最小值和最大值//0 1 2三個數值，但是2-1=2，也就是兩個數值，所以我們需要+1 ,這個差值也就是我們開辟多大的空間int delta = max - min + 1;//創(chuàng)建數組空間int* tmp = (int*)calloc(delta, sizeof(int));if (tmp == NULL){perror("Countsort:tmp:err:");exit(1);//正常退出}//把原數組里面的數值計算之后->存放到tmp數組里面,但是需要控制差值存放在數組里面for (int i = 0; i < n; i++){tmp[a[i] - min]++;}//從數組讀取出，放到原數組里面int j = 0;for (int i = 0; i < delta; i++){while (tmp[i]--){a[j++] = i + min;}} }解釋：
求最小值和最大值：
- 首先初始化?
max?和?min?為數組的第一個元素的值。- 遍歷整個數組?
a，更新?max?和?min?為數組中的最大值和最小值。計算差值：
- 計算最大值和最小值的差值?
delta，這個差值加1后將用于確定計數數組?tmp?的大小。創(chuàng)建計數數組：
- 使用?
calloc?分配一個大小為?delta?的數組?tmp，并將所有元素初始化為0。calloc?會初始化分配的內存為0，這對于計數排序是必要的。計數：
- 遍歷原數組?
a，對于數組中的每個元素?a[i]，計算其與最小值?min?的差值，并在?tmp?數組的相應位置增加計數。例如，如果?a[i]?是3，且?min?是0，則?tmp[3]?會增加1。輸出排序結果：
- 使用兩個指針?
i?和?j，i?用于遍歷?tmp?數組，j?用于指向原數組?a?的當前位置。- 對于?
tmp?數組中的每個非零元素，將其對應的值加回到原數組?a?中，直到?tmp[i]?減至0。這意味著將?min + i?賦值給?a[j]，然后?j?增加，重復這個過程直到?tmp[i]?為0。結束排序：
- 當所有計數都減至0時，原數組?
a?已經是部分有序的，排序完成。錯誤處理：
- 如果?
calloc?分配內存失敗，使用?perror?打印錯誤信息，并調用?exit?退出程序。計數排序的時間復雜度是 O(n + k)，其中 n 是數組
a的長度，k 是整數的范圍（在這個例子中是delta）。由于 k 通常遠小于 n，計數排序對于大量數據的排序非常高效。然而，計數排序的空間復雜度也是 O(k)，如果整數的范圍非常大，它可能需要大量的內存。計數排序是一種穩(wěn)定的排序算法，它不會改變相等元素的相對順序。它特別適用于當數據范圍不大且數據量很大時的場景。
時間復雜度
尋找最大值和最小值：遍歷整個數組以找到最大值和最小值，這個過程的時間復雜度是 O(n)，其中 n 是數組中元素的數量。
創(chuàng)建計數數組：使用
calloc為計數數組分配內存并初始化，這個操作的時間復雜度是 O(k)，其中 k 是最大值和最小值的差值加 1（即整數的范圍）。計數：再次遍歷數組，將每個元素的計數在計數數組中增加。這個過程的時間復雜度也是 O(n)。
輸出排序結果：最后，根據計數數組重建排序后的數組。這個過程涉及遍歷計數數組，并且對于每個非零計數，將對應的元素值放入原數組中。如果計數數組中的非零元素數量接近 n，則這個操作的時間復雜度接近 O(n)。
綜合上述步驟，計數排序的總時間復雜度主要由以下兩個 O(n) 操作決定：
- 尋找最大和最小值
- 計數和輸出排序結果
因此，計數排序的總時間復雜度是 O(n + k)。然而，實際上，當 k（整數的范圍）遠小于 n 時，k 可以被視為一個常數，所以時間復雜度可以簡化為 O(n)。但是，如果 k 很大，接近或大于 n，時間復雜度就接近 O(n + k)。
計數排序的空間復雜度是 O(k)，因為需要額外的計數數組來存儲每個可能整數的出現(xiàn)次數。如果 k 非常大，這可能會成為一個問題。
堆排序
前言
堆排序是速度很快的一種排序方式，尤其是處理大數據的情況下，這個堆排序展現(xiàn)了無與倫比的速度，當然這里比較吃二叉樹篇章，所以我放在了最后，要是有二叉樹理解不深入的，可以看一下這個博客，基本上看完之后就沒有問題了
數據結構-二叉樹系統(tǒng)性學習（四萬字精講拿捏）-CSDN博客
需要在數組里面進行排序，我們可以采取堆排序對其解決問題
版本1：
創(chuàng)建一個數組等大的堆，把數組里面的數值輸入到堆里面進行堆排序，但是這樣的弊端就是，不是順序排序
版本2：
每次我們取堆頂然后打印，最后出堆，循環(huán)
弊端就是這樣是時間復雜度我們發(fā)現(xiàn)還是o(n)，沒有必要那么麻煩半天時間復雜度還是這樣
版本3:（推薦）
在數組上面進行排序，直接輸出順序排序
邏輯講解
1，需要在數組里面進行排序，我們可以采取在數組建堆
2，然后交換收尾元素，每次調整的數值減少1
講解邏輯
首先我們需要知道，
如果我們需要排序的是降序，我們就需要建立小堆
如果我們需要排序的是升序，我們就需要建立大堆
如果我們需要的是升序建立小堆的話
如果我們采取相反的方式的話，就會導致：（出現(xiàn)兩個根）
首先n個數建小堆，固定第一個值是最小值
剩下的n-1個數再建堆
效率就很差了
如果相反的話，會導致根節(jié)點變化，從而導致邏輯混亂，數組里面的數值少的時候是不明顯的，但是多的時候就不行了
邏輯實現(xiàn)圖解
代碼實現(xiàn)
//向下調整（大堆） void AdjustDown(HPDataType* a, int n, int parent) {int chile = parent * 2 + 1;//循環(huán)條件不能是父親，不然會導致越界while (chile < 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;}} } //堆排序數組內進行調整解決 void sort_test(int* a, int sz) {//放出來的是小堆，所以我們只能排序降序，這樣邏輯更融洽//建堆for (int i = 0; i < sz; i++){AdjustUp(a, i);}//交換排序 把首個元素和最后一個交換進行排序 每次--while (sz > 0){Swap(&a[0], &a[sz - 1]);AdjustDown(a, sz - 1, 0);sz--;} }這個
sort_test函數實現(xiàn)了一個堆排序算法，它接收一個整數數組a和它的大小sz：
建堆：首先，函數通過調用
AdjustUp函數來構建一個小頂堆（最小堆）。建堆過程是從最后一個非葉子節(jié)點開始向上調整，直到堆頂。交換和排序：在建堆之后，函數進入一個循環(huán)，每次循環(huán)中，它將堆頂元素（當前堆中的最小元素）與當前堆的最后一個元素交換。然后，堆的大小減少 1，并且對剩余的堆進行向下調整以保持最小堆性質。
循環(huán)結束：循環(huán)繼續(xù)進行，直到堆的大小減小到 0。最終，數組
a將被排序為降序
堆排序衍生的top_k問題
前言
這里本質還是堆排序的衍生問題
也就是還是堆排序問題，我們最終需要學習的就是處理大型數據的問題
?top_k問題時間復雜度的計算
這里提前說明，時間復雜度的計算的目的是來計算向上調整的更優(yōu)還是向下調整更優(yōu)，從肉眼看的話向下調整優(yōu)于向上調整，接下來我們進行時間復雜度的計算。
此時我們會用到等比數列求和以及裂項相消
首先我們需要我們建堆的時候是向上調整，還是向下調整
如圖詳解
首先我們假設求的是滿二叉樹，我們求節(jié)點的個數
滿二叉樹節(jié)點個數
建堆問題：
建堆的話往往的倒數第一個非葉子結點建堆，會時間復雜度最優(yōu)解：也就是
在構建堆（尤其是二叉堆）時，從最后一個非葉子節(jié)點開始進行調整是時間復雜度最優(yōu)解的原因是，這種方法可以減少不必要的調整操作。
為什么從最后一個非葉子節(jié)點開始？
葉子節(jié)點：在完全二叉樹中，葉子節(jié)點不包含任何子節(jié)點，因此不需要進行調整。
非葉子節(jié)點：從最后一個非葉子節(jié)點開始，向上逐個進行調整，可以確保每個節(jié)點在調整時，其子樹已經是堆結構。這樣可以減少調整的深度，因為每個節(jié)點最多只需要與其子節(jié)點交換一次。
減少調整次數：如果從根節(jié)點開始調整，那么每個節(jié)點可能需要多次調整才能達到堆的性質，特別是那些位于樹底部的節(jié)點。而從底部開始，每個節(jié)點只需要調整一次即可。
時間復雜度分析
構建堆的過程涉及對每個非葉子節(jié)點進行調整。對于一個具有 𝑛n 個節(jié)點的完全二叉樹：
葉子節(jié)點：有??𝑛/2?個葉子節(jié)點，它們不需要調整。
非葉子節(jié)點：有??𝑛/2?個非葉子節(jié)點，需要進行調整。
對于非葉子節(jié)點，從最后一個非葉子節(jié)點開始向上調整，每個節(jié)點最多只需要進行 log?𝑘logk（𝑘k 是節(jié)點的深度）次交換。但是，由于樹的結構，底部的節(jié)點不需要進行多次交換，因此整個調整過程的時間復雜度比 𝑂(𝑛log?𝑛) 要低。
實際上，構建堆的時間復雜度是 𝑂(𝑛)，這是因為：
從最后一個非葉子節(jié)點開始，每個節(jié)點的調整次數與其深度成反比。
根節(jié)點的調整次數最多，但只需要一次。
越往下，節(jié)點的深度越小，但需要調整的節(jié)點數量越多。
總結
從最后一個非葉子節(jié)點開始建堆，可以確保每個節(jié)點的調整次數與其深度成反比，從而減少總的調整次數。這種方法利用了完全二叉樹的性質，使得整個建堆過程的時間復雜度達到最優(yōu)，即 𝑂(𝑛)。這是構建堆的最優(yōu)策略，因為它最小化了必要的調整操作，從而提高了算法的效率。
建堆復雜度講解：（向下調整建堆計算）
如圖：
這里為什么-2呢，因為我們的向下調整只是調整h-1層，第h層的節(jié)點的個數是2^h-1，所以第h-1層自然就是-2
所以我們發(fā)現(xiàn)，建堆的時候我們h-1高度的節(jié)點的個數相加得出的結果
為T(n)
所以我們進行計算
從而得出時間復雜度，為什么時間復雜度是高度，因為向下調整的時候，我們循環(huán)終止條件是循環(huán)的高度，也就是當父親節(jié)點不小于sz的時候，所以計算出高度也就計算出了時間復雜度
建堆復雜度講解：（向上調整建堆計算）?
如圖：
計算圖解
所以我們得出結論，這里多了n次
對比
向上調整（
AdjustUp）和向下調整（AdjustDown）的時間復雜度通常與堆的高度相關，即 log?𝑘，其中 𝑘k 是堆中元素的數量。然而，在特定情況下，特別是在構建堆的過程中，這些操作的總時間復雜度可以是 𝑂(𝑛)，這里的 𝑛?是堆中元素的數量。單個操作的時間復雜度：
向上調整 (
AdjustUp)：對于單個元素，向上調整的時間復雜度是 𝑂(log?𝑘)，因為它可能需要從葉子節(jié)點一直調整到根節(jié)點，最多涉及 log?𝑘層的比較和交換。向下調整 (
AdjustDown)：同樣，對于單個元素，向下調整的時間復雜度也是 𝑂(log?𝑘)，因為它可能需要從根節(jié)點調整到葉子節(jié)點，同樣最多涉及 log?𝑘層的比較和交換。構建堆的總時間復雜度：
當我們討論構建一個包含?𝑛?個元素的堆時，所有元素的向上調整操作的總時間復雜度是?𝑂(𝑛)。這是因為：
樹的非葉子節(jié)點大約是?𝑛/2（因為葉子節(jié)點也是?𝑛/2 左右）。
每個非葉子節(jié)點的調整操作最多涉及?log?𝑘 的時間，但是由于樹的結構，從根到葉的路徑上的節(jié)點數量總和大致是?𝑛n。
因此，所有節(jié)點的向上調整操作加起來的時間復雜度是?𝑂(𝑛)。
為什么是?𝑂(𝑛) 而不是?𝑂(𝑛log?𝑘)？
樹的結構特性：在完全二叉樹中，每個層級的節(jié)點數量是指數增長的。從根節(jié)點（1個節(jié)點）到第二層（2個節(jié)點），再到第三層（4個節(jié)點），等等。因此，較低層級的節(jié)點數量遠多于較高層級的節(jié)點數量。
調整深度：根節(jié)點的調整可能需要?log?𝑘 的時間，但較低層級的節(jié)點只需要較少的調整時間。由于底部層級的節(jié)點數量較多，它們較短的調整時間在總體上對總時間復雜度的貢獻較小。
總結：
對于單個元素，向上調整和向下調整的時間復雜度是?𝑂(log?𝑘)
在構建堆的過程中，所有元素的向上調整操作的總時間復雜度是?𝑂(𝑛)，而不是?𝑂(𝑛log?𝑘)，這是由于完全二叉樹的結構特性和調整操作的分布。
因此，向上調整和向下調整在構建堆的過程中的總時間復雜度是 𝑂(𝑛)，而不是 𝑂(log?𝑛)。這個線性時間復雜度是構建堆算法的一個重要特性，使得它在處理大量數據時非常高效。
向上調整和向下調整雖然最后計算的都是O(N)
但是滿二叉樹最后一層占據一半的節(jié)點
所以我們得出結論，向下調整的復雜度優(yōu)于向上調整的復雜度
top_k問題的實現(xiàn)邏輯
1，首先我們創(chuàng)建一個文件，寫入隨機數值1000w個
2，如果需要讀取文件里面最大的10個數值，那么我們就需要，創(chuàng)建一個小堆
原因：
這樣的話，輸入數值的時候，如果讀取的數值比堆頂大，就會替換堆頂從而進堆，然后進行堆排序。
3，在讀取文件的時候，我們需要讀取一個接收一個，然后進行數值的對比，從而進行交換。
4，最后打印最大的數值
5，備注：我們如何判斷我們的找到的最大的前十個數值的正確的，
也是很簡單的，我們設定的隨機數值是10000以內的，然后設定完之后，我們不調用，進入TXT里面更改一些數值。設定一些大于一萬的數值，此時我們就可以發(fā)現(xiàn)我們篩選的數值對不對。
當然如果我們需要找最小的數值，那么我們設定數值最好為-1，因為十萬個數值，很可能是有很多0的。但是我們肉眼看不出來。
top_k計算的代碼實現(xiàn)
//進行計算 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)建空間存儲int* tmp = (int*)malloc(sizeof(int) * k);if (tmp == NULL){perror("TOP_K():Heap* tmp:error");exit(1);}//讀取個數for (int i = 0; i < 10; i++){fscanf(ps, "%d", &tmp[i]);}// 建堆,從最后一個非葉子節(jié)點開始建堆,// 這里的 -1-1 實際上看起來像是一個錯誤。// 通常，當我們需要找到最后一個非葉子節(jié)點的索引以開始建堆過程時，我們會從倒數第二個節(jié)點開始（因為數組索引從0開始）。對于大小為 k 的數組，最后一個非葉子節(jié)點的索引計算如下：// 簡單的說就是，k是數值，我們需要傳參傳遞是下標，找到父親節(jié)點需要減去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問題的實現(xiàn) 小堆尋找最大值 //創(chuàng)建隨機數值 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); } //進行計算 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)建空間存儲int* tmp = (int*)malloc(sizeof(int) * k);if (tmp == NULL){perror("TOP_K():Heap* tmp:error");exit(1);}//讀取個數for (int i = 0; i < 10; i++){fscanf(ps, "%d", &tmp[i]);}// 建堆,從最后一個非葉子節(jié)點開始建堆,// 這里的 -1-1 實際上看起來像是一個錯誤。// 通常，當我們需要找到最后一個非葉子節(jié)點的索引以開始建堆過程時，我們會從倒數第二個節(jié)點開始（因為數組索引從0開始）。對于大小為 k 的數組，最后一個非葉子節(jié)點的索引計算如下：// 簡單的說就是，k是數值，我們需要傳參傳遞是下標，找到父親節(jié)點需要減去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_fopen_w 函數：
- 這個函數用于生成隨機數據并寫入到 "data.txt" 文件中。
- 使用?
fopen?打開文件，如果失敗則打印錯誤并退出程序。- 使用?
srand?和?time?初始化隨機數生成器的種子。- 循環(huán)生成100000個0到9999之間的隨機整數，并使用?
fprintf?將它們寫入文件，每個數字一行。- 最后使用?
fclose?關閉文件。TOP_K 函數：
- 首先定義了要找出的最大的數的個數?
k（這里設置為10）。- 使用?
fopen?打開 "data.txt" 文件進行讀取，如果失敗則打印錯誤并退出程序。- 分配一個大小為?
k?的數組?tmp?用于存儲小頂堆的元素。- 讀取前10個數字存入?
tmp?數組中，這里假設文件中的數字至少有10個。建堆：
- 從最后一個非葉子節(jié)點開始調整堆，以確保?
tmp?數組是一個有效的小頂堆。這里的注釋提到 "-1-1 實際上看起來像是一個錯誤"，但實際上，計算最后一個非葉子節(jié)點的索引是正確的。對于大小為?k?的完全二叉樹，最后一個非葉子節(jié)點的索引是?(k - 2) / 2。這里的計算?(k - 1 - 1) / 2?實際上得到的是倒數第二個非葉子節(jié)點的索引- 使用?
AdjustDown?函數從最后一個非葉子節(jié)點開始向下調整堆，確保堆的性質。排序：
- 使用?
fscanf?從文件中讀取數字，直到文件結束（EOF）。- 對于每個讀取的數字，如果它大于堆頂（即?
tmp[0]），則替換堆頂元素，并調用?AdjustDown?函數向下調整堆。- 這個過程確保了?
tmp?數組中始終存儲著當前讀取到的最大的K個數。打印結果：
- 循環(huán)打印?
tmp?數組中的所有元素，這些元素就是最大的K個數。- 使用?
fclose?關閉文件。注意：
- 代碼中沒有提供?
AdjustDown?函數的實現(xiàn)，這個函數用于向下調整堆，以保持堆的性質。- 代碼假設文件中的數字數量至少為10，如果少于10個，需要額外的錯誤處理。
- 代碼中沒有考慮內存分配失敗的情況，實際使用中應該檢查?
malloc?的返回值。整體上，這段代碼展示了如何使用小頂堆來解決TOP-K問題，通過維護一個大小為K的最小堆，可以有效地找到數據流中最大的K個數。