使用Java實現計數排序算法

計數排序是一種簡單直觀的非比較型排序算法，它通過統計每個元素出現的次數，再根據這些次數確定元素在排序後的位置。這種算法在元素範圍較小且重複元素較多的場景下效率極高，非常適合初學者理解和實現。

算法核心思路¶

確定元素範圍：找出待排序數組中的最小值min和最大值max，確定元素的取值範圍爲[min, max]。
統計元素次數：創建一個計數數組，長度爲max - min + 1，用於記錄每個元素出現的次數。
計算前綴和：將計數數組轉換爲前綴和數組，此時數組中每個位置的值表示對應元素在排序後的最後一個位置。
生成排序結果：從原數組末尾開始遍歷，根據元素的計數位置將其放入結果數組，確保排序穩定性。

代碼實現步驟¶

1. 處理邊界情況¶

若數組爲空或僅有一個元素，直接返回，無需排序。

2. 確定元素範圍¶

遍歷數組找到最小值min和最大值max，計算元素範圍大小max - min + 1。

3. 統計元素出現次數¶

創建計數數組count，長度爲max - min + 1。遍歷原數組，將每個元素num映射到count[num - min]位置並計數。

4. 計算前綴和¶

對計數數組進行累加，得到每個元素在排序後的最後一個位置。

5. 生成排序結果¶

從原數組末尾遍歷，根據元素的映射位置和前綴和數組，將元素放入結果數組的正確位置。

Java代碼實現¶

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {
        // 邊界情況處理：空數組或單元素數組無需排序
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 步驟1：找出數組中的最小值和最大值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        // 步驟2：創建計數數組，長度爲max - min + 1
        int[] count = new int[max - min + 1];

        // 步驟3：統計每個元素出現的次數
        for (int num : arr) {
            count[num - min]++; // 映射元素到計數數組的索引（避免負數）
        }

        // 步驟4：計算前綴和（累加），得到每個元素的最後位置
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 步驟5：生成排序結果數組（從後往前遍歷保證穩定性）
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int k = num - min; // 元素對應的計數數組索引
            result[count[k] - 1] = num; // 放置元素到結果數組的對應位置
            count[k]--; // 減少計數，爲下一個重複元素騰出位置
        }

        // 將結果數組複製回原數組
        System.arraycopy(result, 0, arr, 0, arr.length);
    }

    // 測試代碼
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("排序前：" + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("排序後：" + Arrays.toString(arr));
    }
}

代碼解釋¶

統計次數：通過num - min將元素映射到計數數組的非負索引，避免負數索引問題。例如，元素2在min=1時，映射到索引1（2-1=1）。
前綴和計算：累加後的計數數組中，每個位置i的值表示元素min + i在排序後的最後一個位置。例如，原數組[1,2,2,3,3,4,8]的計數數組累加後爲[1,3,5,6,6,6,6,7]，其中count[2]=5表示元素3（min+2=3）的最後位置是4（5-1）。
穩定性：從原數組末尾遍歷，確保重複元素的相對順序不變。例如，原數組中的兩個2會按原順序放在結果數組的第1和第2位置。

複雜度分析¶

時間複雜度：O(n + k)，其中n是數組長度，k是元素範圍大小（max - min + 1）。只需遍歷數組3次（統計、累加、生成結果）。
空間複雜度：O(n + k)，需要額外的計數數組和結果數組。

適用場景¶

元素爲整數且範圍較小（如學生分數、年齡等）。
重複元素較多，且需要保持相對順序（穩定性）。

計數排序通過簡單的計數和累加操作實現排序，無需複雜的比較邏輯，非常適合初學者理解排序算法的基本思想。