經典演算法：基數排序 原理、C# 實作與效能分析

前言

基數排序 是非比較型整數排序演算法，透過「位數」將資料分桶排序，時間複雜度 O(k·n)（k 為最大位數，n 為元素數），在特定條件下快於 O(n log n) 的比較排序。本文詳細說明原理、逐步演示、C# 完整實作、適用場景與優缺點。

核心原理

1. 統一位數：所有正整數補齊至相同位數（高位補 0）。
2. 從最低位 (LSD) 開始：依個位、十位、百位…逐輪排序。
3. 穩定排序：每輪以 Counting Sort（計數排序）為子程序，保持相同關鍵字的相對順序。
4. 完成最高位：序列即有序。

逐步演示

陣列：[62, 14, 59, 88, 16]，最大 2 位數。

第 1 輪：個位數分桶

桶 0: -
桶 1: -
桶 2: 62
桶 3: -
桶 4: 14
桶 5: -
桶 6: 16
桶 7: -
桶 8: 88
桶 9: 59

收集：[62, 14, 16, 88, 59]

第 2 輪：十位數分桶

桶 0: -
桶 1: 14, 16   (個位已有序)
桶 2: -
桶 3: -
桶 4: -
桶 5: 59
桶 6: 62
桶 7: -
桶 8: 88
桶 9: -

收集：[14, 16, 59, 62, 88] → 排序完成。

C# 完整實作

using System;

public static class RadixSort
{
    /// 

    /// 基數排序 (LSD, 僅支援非負整數)
    /// 
    /// 待排序陣列
    /// 最大位數（可自動計算）
    public static void Sort(int[] array, int maxDigits = -1)
    {
        if (array == null || array.Length <= 1) return;

        // 自動計算最大位數
        if (maxDigits <= 0)
        {
            int max = array[0];
            for (int i = 1; i < array.Length; i++)
                if (array[i] > max) max = array[i];
            
            maxDigits = max == 0 ? 1 : (int)Math.Log10(max) + 1;
        }

        int[] temp = new int[array.Length];
        int[] count = new int[10]; // 0-9 十個桶

        for (int digit = 1; digit <= maxDigits; digit++)
        {
            int divisor = (int)Math.Pow(10, digit - 1);

            // 1. 計數：統計各桶元素數量
            Array.Clear(count, 0, 10);
            for (int i = 0; i < array.Length; i++)
            {
                int bucket = (array[i] / divisor) % 10;
                count[bucket]++;
            }

            // 2. 累積計數：轉換為目標索引 (穩定排序關鍵)
            for (int i = 1; i < 10; i++)
                count[i] += count[i - 1];

            // 3. 從後往前放入暫存陣列 (保持穩定性)
            for (int i = array.Length - 1; i >= 0; i--)
            {
                int bucket = (array[i] / divisor) % 10;
                temp[--count[bucket]] = array[i];
            }

            // 4. 複製回原陣列
            Array.Copy(temp, array, array.Length);
        }
    }

    /// 

    /// 支援負數的基數排序（分離正負、各自排序、合併）
    /// 
    public static void SortWithNegatives(int[] array)
    {
        if (array == null || array.Length <= 1) return;

        var negatives = new System.Collections.Generic.List<int>();
        var nonNegatives = new System.Collections.Generic.List<int>();

        foreach (var n in array)
        {
            if (n < 0) negatives.Add(-n); // 存絕對值
            else nonNegatives.Add(n);
        }

        // 負數排序後反轉並加回負號
        if (negatives.Count > 0)
        {
            Sort(negatives.ToArray());
            negatives.Reverse();
            for (int i = 0; i < negatives.Count; i++)
                negatives[i] = -negatives[i];
        }

        if (nonNegatives.Count > 0)
            Sort(nonNegatives.ToArray());

        // 合併
        int idx = 0;
        foreach (var n in negatives) array[idx++] = n;
        foreach (var n in nonNegatives) array[idx++] = n;
    }
}

單元測試

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        // 基本測試
        int[] arr1 = { 62, 14, 59, 88, 16, 0, 5, 1000, 999 };
        Console.WriteLine("原始: " + string.Join(", ", arr1));
        RadixSort.Sort(arr1);
        Console.WriteLine("排序: " + string.Join(", ", arr1));
        Console.WriteLine("驗證: " + arr1.SequenceEqual(arr1.OrderBy(x => x)));

        // 負數測試
        int[] arr2 = { -5, 100, -1, 0, 42, -999, 3 };
        Console.WriteLine("\n原始: " + string.Join(", ", arr2));
        RadixSort.SortWithNegatives(arr2);
        Console.WriteLine("排序: " + string.Join(", ", arr2));
        Console.WriteLine("驗證: " + arr2.SequenceEqual(arr2.OrderBy(x => x)));

        // 大量資料效能測試
        var rnd = new Random(42);
        int[] big = Enumerable.Range(0, 1_000_000).Select(_ => rnd.Next(0, 10_000_000)).ToArray();
        var sw = System.Diagnostics.Stopwatch.StartNew();
        RadixSort.Sort(big);
        sw.Stop();
        Console.WriteLine($"\n1,000,000 元素排序耗時: {sw.ElapsedMilliseconds} ms");
        Console.WriteLine("驗證: " + big.SequenceEqual(big.OrderBy(x => x)));
    }
}

效能分析

何時選用基數排序？

• 資料為非負整數（或可轉換為整數的固定格式）。
• n 很大（> 10^5），且 k 較小（位數 < 10）：O(k·n) 顯著優於 O(n log n)。
• 需要穩定排序。
• 記憶體允許額外 O(n) 空間。

缺點與限制

• 不適用於浮點數（需特殊編碼）、任意長度字串、自訂比較器物件。
• k 過大（如 64-bit 整數 k=19/20）時，常數因子大，反而比 QuickSort 慢。
• 非原地排序，需額外陣列。
• 負數需額外處理（分離正負、絕對值排序、合併）。

進階變體

MSD (Most Significant Digit) 基數排序

從最高位遞迴分桶，適合字串排序，可提前終止（前綴相同者不再深入）。

混合演算法

小桶改用 Insertion Sort；大桶繼續基數排序。.NET Array.Sort 內部即採用 Introspective Sort（QuickSort + HeapSort + InsertionSort），不直接使用基數排序。

總結

• 基數排序是特定領域（整數、大量資料、低位數）的極致效能選擇。
• 核心是穩定的計數排序作為子程序，逐位分桶收集。
• C# 實作關鍵：(value / divisor) % 10 取得指定位數、累積計數轉索引、逆向填入暫存陣列保持穩定性。
• 實務上若資料型別多樣或 n 不大，Array.Sort / List.Sort 仍是最佳預設選擇。