---

前言

今天我們一起來了解歸并排序（MergeSort），以及一種非比較的計(jì)數(shù)排序（CountSort）~

---

一、歸并排序

1. 歸并排序的思想

歸并排序（Merge Sort）是一種基于分治法（Divide and Conquer）的高效排序算法。它的核心步驟包括將一個(gè)數(shù)組分割成更小的子數(shù)組，對(duì)這些子數(shù)組進(jìn)行排序，然后將它們合并成一個(gè)有序的數(shù)組。以下是歸并排序的核心步驟詳解：

歸并排序的核心步驟：

1. 分割（Divide）：

   • 將待排序數(shù)組從中間分割成兩個(gè)子數(shù)組（通常是左半部分和右半部分）。
   • 繼續(xù)遞歸地將這兩個(gè)子數(shù)組再分割，直到每個(gè)子數(shù)組的大小為 1（即只有一個(gè)元素），因?yàn)橐粋€(gè)元素的數(shù)組是有序的。

2. 歸并（Merge）：

   • 將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。
   • 使用兩個(gè)指針分別指向兩個(gè)子數(shù)組的開頭，比較指針指向的元素，將較小的元素放入新數(shù)組中，并移動(dòng)相應(yīng)的指針。
   • 當(dāng)其中一個(gè)子數(shù)組的元素被全部放入新數(shù)組后，將另一個(gè)子數(shù)組剩余的元素直接復(fù)制到新數(shù)組的后面。

3. 組合（Combine）：

   • 在歸并的過程中，逐步形成更大的有序數(shù)組，最終得到一個(gè)完整的有序數(shù)組。

總結(jié)：
歸并排序是一種高效的排序算法，利用分治法的思想，通過將大問題分解為小問題來解決。其穩(wěn)定性、時(shí)間復(fù)雜度 O(n log n) 以及適用于大規(guī)模數(shù)據(jù)的特性使其在實(shí)際應(yīng)用中非常流行。

我們一起來看下面的圖：

通過這張圖我們可以很直觀的感受到歸并排序的分解和合并過程，它的步驟是這樣的：

歸并排序步驟總結(jié) ：

1. 定義歸并排序主函數(shù)：

   • MergeSort 函數(shù)接受待排序數(shù)組和數(shù)組的大小作為參數(shù)。
   • 在函數(shù)中分配一個(gè)臨時(shí)數(shù)組 tmp，用于輔助合并數(shù)組。其實(shí)我們合并出來的數(shù)據(jù)是在tmp中的，最后拷貝回去。
   • 調(diào)用 _MergeSort 函數(shù)進(jìn)行排序。

   void MergeSort(int* arr, int n) {int* tmp = (int*)malloc(sizeof(int) * n); // 創(chuàng)建臨時(shí)數(shù)組_MergeSort(arr, 0, n - 1, tmp); // 調(diào)用歸并排序free(tmp); // 釋放臨時(shí)數(shù)組
   }
   

2. 定義歸并排序遞歸函數(shù)：

   • _MergeSort 函數(shù)接受數(shù)組、左邊界、右邊界和臨時(shí)數(shù)組作為參數(shù)。
   • 基本情況：如果 left 大于或等于 right，則返回，表示該子數(shù)組已經(jīng)有序。

   void _MergeSort(int* arr, int left, int right, int* tmp) {if (left >= right) {return; // 基本情況}...
   }
   

3. 分割數(shù)組：

   • 計(jì)算中間索引 mid，將數(shù)組分割為左右兩個(gè)部分。
   • 遞歸調(diào)用 _MergeSort 對(duì)左半部分（left 到 mid）和右半部分（mid + 1 到 right）進(jìn)行排序。

   
   對(duì)于它的每一個(gè)左右兩側(cè)都要繼續(xù)分割（以左側(cè)為例）：
   

   int mid = (left + right) / 2;
   _MergeSort(arr, left, mid, tmp); // 遞歸排序左半部分
   _MergeSort(arr, mid + 1, right, tmp); // 遞歸排序右半部分
   

4. 合并有序子數(shù)組：

   • 定義兩個(gè)指針 begin1 和 begin2，分別指向左子數(shù)組和右子數(shù)組的起始位置。
   • 使用 index 指針在臨時(shí)數(shù)組 tmp 中進(jìn)行合并。

   

   int begin1 = left, end1 = mid; // 左子數(shù)組范圍
   int begin2 = mid + 1, end2 = right; // 右子數(shù)組范圍
   int index = begin1; // 臨時(shí)數(shù)組下標(biāo)while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) {tmp[index++] = arr[begin1++]; // 復(fù)制較小的元素} else {tmp[index++] = arr[begin2++];}
   }
   

5. 處理剩余元素：

   • 如果左子數(shù)組還有剩余元素，將其復(fù)制到 tmp 中。
   • 如果右子數(shù)組還有剩余元素，也將其復(fù)制到 tmp 中。

   while (begin1 <= end1) {tmp[index++] = arr[begin1++]; // 復(fù)制左子數(shù)組剩余元素
   }
   while (begin2 <= end2) {tmp[index++] = arr[begin2++]; // 復(fù)制右子數(shù)組剩余元素
   }
   

6. 將合并結(jié)果復(fù)制回原數(shù)組：

   • 將臨時(shí)數(shù)組 tmp 中的有序元素復(fù)制回原數(shù)組 arr 的相應(yīng)位置。

   for (int i = left; i <= right; i++) {arr[i] = tmp[i]; // 將臨時(shí)數(shù)組的內(nèi)容復(fù)制回原數(shù)組
   }
   

---

2. 歸并排序時(shí)間復(fù)雜度及空間復(fù)雜度

歸并排序（Merge Sort）是一種高效的排序算法，其時(shí)間復(fù)雜度和空間復(fù)雜度如下：

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

• 歸并排序的時(shí)間復(fù)雜度為 O(n log n)：

  • 分割階段：每次將數(shù)組分成兩個(gè)子數(shù)組，深度為 log n，表示分割的層數(shù)。

  • 合并階段：在每一層中，合并兩個(gè)子數(shù)組的過程需要 O(n) 的時(shí)間，因?yàn)槊總€(gè)元素都要被處理一次。

  • 因此，整個(gè)算法的時(shí)間復(fù)雜度可以表示為：
    

  • 根據(jù)主定理，得到歸并排序的時(shí)間復(fù)雜度為 O(n log n)。

空間復(fù)雜度 :

• 歸并排序的空間復(fù)雜度為 O(n)：
  • 歸并排序需要使用額外的臨時(shí)數(shù)組來存儲(chǔ)合并過程中的結(jié)果。在每次合并操作中，都會(huì)分配一個(gè)大小為 n 的臨時(shí)數(shù)組，因此其空間復(fù)雜度為 O(n)。

總結(jié) ：

• 時(shí)間復(fù)雜度：O(n log n)
• 空間復(fù)雜度：O(n)

---

3. 歸并排序代碼實(shí)現(xiàn)

1）遞歸版本

//歸并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;//index 為tmp下標(biāo)，不一定是0，而是左邊界int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

---

2）非遞歸版本

/*
非遞歸排序與遞歸排序相反，將一個(gè)元素與相鄰元素構(gòu)成有序數(shù)組，
再與旁邊數(shù)組構(gòu)成有序數(shù)組，直至整個(gè)數(shù)組有序。
要有mid指針傳入，因?yàn)椴蛔阋唤M數(shù)據(jù)時(shí)，重新計(jì)算mid劃分會(huì)有問題
需要指定mid的位置
*/
void merge(int* a, int left, int mid, int right, int* tmp)
{// [left, mid]// [mid+1, right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])tmp[index++] = a[begin1++];elsetmp[index++] = a[begin2++];}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}/*
k用來表示每次k個(gè)元素歸并
*/
void mergePass(int* arr, int k, int n, int* temp)
{int i = 0;//從前往后,將2個(gè)長(zhǎng)度為k的子序列合并為1個(gè)while (i < n - 2 * k + 1){merge(arr, i, i + k - 1, i + 2 * k - 1, temp);i += 2 * k;}//合并區(qū)間[i, n - 1]有序的左半部分[i, i + k - 1]以及不及一個(gè)步長(zhǎng)的右半部分[i + k, n - 1]if (i < n - k){merge(arr, i, i + k - 1, n - 1, temp);}}

---

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

1. 計(jì)數(shù)排序的思想

計(jì)數(shù)排序是一種非比較排序算法，適用于范圍有限的整數(shù)數(shù)據(jù)。它的核心思想是利用數(shù)組的索引來直接計(jì)算元素的位置，達(dá)到排序的目的。
1）統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
2）根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列

我們來看下面這張圖：

這是我們待排序的數(shù)組。

• 第一步：定義一個(gè)新數(shù)組，使得舊數(shù)組的元素值是新數(shù)組的下標(biāo)

假設(shè)，我們定義成這樣行不行？

如果完全按照舊數(shù)組的元素值來開空間會(huì)造成大量的空間浪費(fèi)，因此不可取。

這里還有一個(gè)問題，如果舊數(shù)組的元素值是負(fù)數(shù)怎么辦呢？

這里空間問題可以和負(fù)數(shù)問題一起解決：

首先找到舊數(shù)組的最小值，以及最大值

遍歷一遍數(shù)組很容易找到數(shù)組最小值為100，最大值為109.

那我們開的空間 range 就是最值差

• 第二步：舊數(shù)組中每一個(gè)元素減去最小值min作為新數(shù)組下標(biāo)，出現(xiàn)了幾個(gè)新數(shù)組對(duì)應(yīng)的下標(biāo)中的元素就是多少，這樣也順便解決了負(fù)數(shù)問題，因?yàn)樨?fù)數(shù) - 更小的負(fù)數(shù) = 正數(shù)。

• 第三步：遍歷新數(shù)組，只要數(shù)組數(shù)據(jù)不為零就循環(huán)次數(shù)（數(shù)組值），輸出內(nèi)容 （i + min），將所有元素拷貝回原來的數(shù)組，就完成了排序。
  

---

2. 計(jì)數(shù)排序的時(shí)間復(fù)雜度及空間復(fù)雜度

計(jì)數(shù)排序是一種有效的排序算法，特別適用于數(shù)據(jù)范圍有限的情況。根據(jù)你提供的代碼，以下是計(jì)數(shù)排序的時(shí)間復(fù)雜度和空間復(fù)雜度分析：

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

計(jì)數(shù)排序的時(shí)間復(fù)雜度為 O(n + k)，其中：

• n：待排序數(shù)組的大小。
• k：待排序元素的范圍（最大值 - 最小值 + 1）。

分析過程：

1. 找最大最小值：遍歷數(shù)組一次，找到最大值和最小值，時(shí)間復(fù)雜度為 O(n)。
2. 創(chuàng)建計(jì)數(shù)數(shù)組：分配大小為 k 的計(jì)數(shù)數(shù)組，時(shí)間復(fù)雜度為 O(k)。
3. 統(tǒng)計(jì)元素出現(xiàn)次數(shù)：再次遍歷原數(shù)組，將每個(gè)元素的出現(xiàn)次數(shù)記錄在計(jì)數(shù)數(shù)組中，時(shí)間復(fù)雜度為 O(n)。
4. 放回排序結(jié)果：遍歷計(jì)數(shù)數(shù)組，根據(jù)記錄的次數(shù)將元素放回原數(shù)組，最壞情況下需要遍歷 k 次，時(shí)間復(fù)雜度為 O(k)。

因此，總的時(shí)間復(fù)雜度為：

空間復(fù)雜度 ：

計(jì)數(shù)排序的空間復(fù)雜度為 O(k)，其中 k 是待排序元素的范圍。

分析過程：

• 需要一個(gè)計(jì)數(shù)數(shù)組 count，其大小為 k，用于存儲(chǔ)每個(gè)元素出現(xiàn)的次數(shù)。
• 如果輸出數(shù)組與原數(shù)組相同，空間復(fù)雜度會(huì)增加到 O(n + k)（包含原數(shù)組和計(jì)數(shù)數(shù)組），但通常我們只考慮額外空間，因此空間復(fù)雜度通常記為 O(k)。

總結(jié)

• 時(shí)間復(fù)雜度：O(n + k)
• 空間復(fù)雜度：O(k)

這種復(fù)雜度特性使得計(jì)數(shù)排序在處理范圍有限的整數(shù)數(shù)據(jù)時(shí)非常高效。適合用于大規(guī)模的正整數(shù)排序，尤其在數(shù)值分布相對(duì)均勻的情況下。
但缺點(diǎn)也很明顯，數(shù)據(jù)過于分散太浪費(fèi)空間，而且只能處理整數(shù)數(shù)據(jù)！

---

3. 計(jì)數(shù)排序代碼實(shí)現(xiàn)

// 計(jì)數(shù)排序
void CountSort(int* arr, int n)
{int max = arr[0], min = arr[0];//找最大最小值for (int i = 1; i < n; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}//定義新數(shù)組空間大小int range = max - min + 1;int* count = (int*)malloc(range * sizeof(int));if (count == NULL){perror("malloc fail!");exit(1);}//初始化range數(shù)組中所有的數(shù)據(jù)為0memset(count, 0, sizeof(int) * range);//原來的下標(biāo)成為元素，原來的(元素 - min) 成為下標(biāo)，出現(xiàn)幾次新的元素就加幾次for (int i = 0; i < n; i++){count[arr[i] - min]++;}//把排好序的元素放回原數(shù)組int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}

---

總結(jié)（排序算法穩(wěn)定性）

到了這里我們所有排序思想已經(jīng)學(xué)完了，再來一起總結(jié)一下吧！

排序算法復(fù)雜度及穩(wěn)定性分析：

穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的
相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，?在排序后的序列中，r[i]仍在r[j]之
前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

謝謝大家~