什麼是計數排序？¶

計數排序是一種非比較型的排序算法，它的核心思想是通過統計每個元素出現的次數，然後根據這些次數直接構建排序後的數組。與快速排序、歸併排序等基於比較的排序算法不同，計數排序不需要比較元素的大小，而是通過“計數”的方式完成排序。這種算法特別適合處理整數範圍不大的排序場景，比如學生成績（0-100分）、年齡（0-150歲）等數據。

基本思路¶

以一個具體例子說明計數排序的步驟：假設我們要對數組 [4, 2, 2, 8, 3, 3, 1] 進行排序。

1. 統計元素出現次數：
   首先找到數組中的最大值（這裏是8），創建一個大小爲 max_val + 1 的計數數組 count，用於記錄每個元素出現的次數。遍歷原數組，統計每個元素的出現次數：
   - count[0] = 0（無0）
   - count[1] = 1（元素1出現1次）
   - count[2] = 2（元素2出現2次）
   - count[3] = 2（元素3出現2次）
   - count[4] = 1（元素4出現1次）
   - count[5] = 0（無5）
   - count[6] = 0（無6）
   - count[7] = 0（無7）
   - count[8] = 1（元素8出現1次）

2. 構建排序數組：
   根據計數數組的統計結果，將元素按順序插入到結果數組中。例如：
   - 元素1出現1次 → 插入結果數組：[1]
   - 元素2出現2次 → 插入結果數組：[1, 2, 2]
   - 元素3出現2次 → 插入結果數組：[1, 2, 2, 3, 3]
   - 元素4出現1次 → 插入結果數組：[1, 2, 2, 3, 3, 4]
   - 元素8出現1次 → 插入結果數組：[1, 2, 2, 3, 3, 4, 8]

C++代碼實現¶

下面是計數排序的完整C++實現：

#include <iostream>
using namespace std;

// 計數排序函數：對數組arr進行排序
void countingSort(int arr[], int n) {
    // 步驟1：找到數組中的最大值
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    // 步驟2：創建計數數組，大小爲max_val + 1，初始化爲0
    int count[max_val + 1] = {0};

    // 步驟3：統計每個元素出現的次數
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 步驟4：構建排序後的數組
    int output[n]; // 結果數組
    int index = 0; // 結果數組的當前索引
    for (int i = 0; i <= max_val; i++) {
        // 將元素i重複count[i]次插入到結果數組
        while (count[i] > 0) {
            output[index] = i;
            index++;
            count[i]--;
        }
    }

    // 步驟5：將排序後的結果複製回原數組
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 測試函數
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前的數組: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    countingSort(arr, n);

    cout << "\n排序後的數組: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

代碼解釋¶

1. 找到最大值：遍歷數組確定最大元素，用於創建計數數組的大小。
2. 統計次數：通過計數數組 count 記錄每個元素出現的次數，例如 count[2] = 2 表示元素2出現2次。
3. 構建結果數組：遍歷計數數組，將每個元素按出現次數重複插入結果數組 output。
4. 複製回原數組：將排序後的結果數組 output 複製回原數組 arr，完成排序。

時間複雜度與空間複雜度¶

• 時間複雜度：O(n + k)，其中 n 是數組長度，k 是最大值與最小值的差。遍歷數組統計次數需要 O(n)，構建結果數組需要 O(n)，總時間爲 O(n + k)。
• 空間複雜度：O(k)，需要額外的計數數組 count 和結果數組 output，空間大小取決於最大值 k。

適用場景與注意事項¶

• 適用場景：
• 待排序元素爲非負整數且範圍較小（如學生成績、年齡）。

• 需高效排序且不關心元素間的相對順序（僅需穩定排序時需額外處理）。

• 處理負數的方法：若數組包含負數，可通過“偏移量”將負數轉換爲非負數。例如，數組 [-1, 3, -2] 的最小值爲 -2，可將每個元素加上 2（偏移量）轉換爲 [1, 5, 0]，排序後再減去偏移量。

通過上述步驟，計數排序能以線性時間完成排序，是處理小範圍整數的高效算法。初學者只需理解“統計次數→構建結果”的核心邏輯，即可快速掌握其實現。