💬 歡迎討論：在閱讀過程中有任何疑問，歡迎在評論區留言，我們一起交流學習！
👍 點贊、收藏與分享：如果你覺得這篇文章對你有幫助，記得點贊、收藏，并分享給更多對數據結構感興趣的朋友！

前言

本文主要內容是歸并的遞歸和非遞歸以及計數排序的實現方法。文章會提及很多容易忽視的易錯點（大多是我自己踩過的坑😂），這是我在學習這塊內容時獲取的教訓和寶貴經驗。

因為自己淋過雨，希望能為你們撐把傘！共勉！😁

---

一、歸并排序（Merge Sort）

1. 算法原理

基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序核心步驟：

1. 分解：將數組遞歸分成兩半，直到子數組長度為1。
2. 合并：將兩個有序子數組合并為一個有序數組。

從步驟可以看出，這似乎就是二叉樹的后序遍歷

不知道你們在學習C語言的時候有沒有寫過這樣一道題
合并兩個有序數組
我建議沒寫過的可以去寫一下，這里可以直接抄作業了，O(∩_∩)O哈哈~

2. 遞歸實現

1. 首先我們需要開辟一個臨時數組，來存儲合并的序列

2. 遞歸結束條件：數組長度為1時結束
   if (left >= right) return;

3. mid不要寫成(right - left) / 2了，再加上left才能在正確位置（因為這是在計算下標），或者直接用（right+left）/2。——易錯點

4. 確定每次拆分的區間[left，mid] [mid + 1,right]。

5. 遞歸（后序遍歷），

6. 歸并：在tmp上正確的位置進行賦值，不能是cur = 0,否則會覆蓋值——易錯點

7. 拷貝，將tmp拷貝到a

void Merger(int* a, int* tmp, int left, int right)
{//遞歸結束條件if (left >= right) {return;}int mid = left + (right - left) / 2;//易錯：加上left才能在正確的位置//遞歸（后序遍歷）//[left,mid] [mid+1,right]Merger(a, tmp, left, mid);Merger(a, tmp, mid+1, right);//歸并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int cur = left;//易錯：在tmp上正確的位置進行賦值，不能是cur = 0,否則會覆蓋值while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] > a[begin2]) {tmp[cur++] = a[begin2++];}else {tmp[cur++] = a[begin1++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}//將tmp拷貝到amemcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}void MergerSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int begin = 0, end = n - 1;Merger(a, tmp, begin, end);free(tmp);
}

特點：

• 時間復雜度：O(n log n)
• 空間復雜度：O(n)
• 穩定排序，適合處理大數據量。

---

3. 非遞歸實現

利用迭代（循環）模擬遞歸過程：

當元素個數不是gap的整數時，會發生越界問題：
設歸并的兩部分分別為[begin1,end1]和[begin2,end2]
那么，end1、begin2、end2都可能會越界，因此我們就需要修正邊界。

1. end1越界時，第一部分不完整且第二部分不存在，沒必要歸并了，直接拷貝即可
2. begin2越界時，第二部分不存在，沒必要歸并了，直接拷貝即可
3. end2越界時，第二部分不完整，將end2修正到數組末尾即可

可以發現，1,2是一類情況，可以一起處理了。

我們需要來抉擇一個問題：

1. 整體歸并結束后拷貝
2. 歸并一部分拷貝一部分

這兩個問題看似不起眼，實則不然，它會影響你控制邊界的難度。可以試試兩種方式都寫寫，會特別爽（狗頭）

1. 歸并結束后再拷貝，需精密控制邊界越界情況，容易出錯。——不推薦該寫法

void MergerSortNonR1(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap) {//歸并//[i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int cur = i;if (end1 >= n) {//修正end1end1 = n - 1;//使得begin2 > end2,終止歸并begin2 = n;end2 = n - 1;}else if (begin2 >= n) {//使得begin2 > end2,終止歸并begin2 = n;end2 = n - 1;}else if (end2 >= n) {//修正end2，繼續歸并end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] > a[begin2]) {tmp[cur++] = a[begin2++];}else {tmp[cur++] = a[begin1++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}}//歸并結束后再打印memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}

2. 歸并一次拷貝一次，若end1與begin2有越界情況，直接跳出循環（退出歸并）即可無需控制邊界情況，操作簡單易理解

void MergerSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap) {//歸并//[i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int cur = i;if (end1 >= n || begin2 >= n) {break;//直接終止歸并}else if (end2 >= n) {//修正end2end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] > a[begin2]) {tmp[cur++] = a[begin2++];}else {tmp[cur++] = a[begin1++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}//歸并一次打印一次memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}//printf("\n");gap *= 2;}free(tmp);
}

關鍵點：

• gap 控制合并步長，從1開始逐步擴大。
• 邊界處理：若子數組越界，直接終止合并。

---

二、計數排序（Count Sort）

思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。 操作步驟：

1. 統計相同元素出現次數
2. 根據統計的結果將序列回收到原來的序列中

1. 算法原理

1. 確定范圍：找出數組的最小值 min 和最大值 max。
2. 統計頻率：創建計數數組 countA，統計每個元素出現的次數。
3. 重建數組：根據計數數組將元素按順序寫回原數組。
   

2. 代碼實現

void CountSort(int* a, int n) {int min = a[0], max = a[0];for (int i = 0; i < n; i++) {   // 確定范圍if (a[i] < min) min = a[i];if (a[i] > max) max = a[i];}int range = max - min + 1;int* countA = (int*)calloc(range, sizeof(int));  // 分配計數數組for (int i = 0; i < n; i++) countA[a[i] - min]++; // 統計頻率// 重建數組int cur = 0;for (int i = 0; i < range; i++) {while (countA[i]--) a[cur++] = i + min;}free(countA);
}

特點：

• 時間復雜度：O(n + k)，k 為數據范圍。
• 空間復雜度：O(k)
• 非比較排序，適合數據范圍小且為整數的情況。

---

三、對比與總結

算法	時間復雜度	空間復雜度	穩定性	適用場景
歸并排序	O(n log n)	O(n)	穩定	大數據量、需穩定排序
計數排序	O(n + k)	O(k)	穩定	小范圍整數、非比較排序

希望這篇文章對你有所幫助🌹🌹🌹