C# 四大經典排序演算法實作：冒泡、選擇、插入、希爾排序

前言

排序演算法是程式設計基礎。本文提供四種經典排序的 C# 實作，並分析時間複雜度、穩定性與適用場景。所有範例採用泛型與 IComparer<T>，支援任意可比較型別。

演算法複雜度對比

統一介面定義

public interface ISorter
{
    void Sort(T[] array, IComparer comparer = null);
}

public static class SortExtensions
{
    public static void Sort(this T[] array) where T : IComparable
        => Array.Sort(array); // 內建 Timsort (混合插入+歸併)
}

1. 冒泡排序

public class BubbleSorter : ISorter
{
    public void Sort(T[] array, IComparer comparer = null)
    {
        comparer ??= Comparer.Default;
        int n = array.Length;
        bool swapped;
        
        for (int i = 0; i < n - 1; i++)
        {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (comparer.Compare(array[j], array[j + 1]) > 0)
                {
                    (array[j], array[j + 1]) = (array[j + 1], array[j]);
                    swapped = true;
                }
            }
            if (!swapped) break; // 提前結束優化
        }
    }
}

2. 選擇排序

public class SelectionSorter : ISorter
{
    public void Sort(T[] array, IComparer comparer = null)
    {
        comparer ??= Comparer.Default;
        int n = array.Length;
        
        for (int i = 0; i < n - 1; i++)
        {
            int minIdx = i;
            for (int j = i + 1; j < n; j++)
            {
                if (comparer.Compare(array[j], array[minIdx]) < 0)
                    minIdx = j;
            }
            if (minIdx != i)
                (array[i], array[minIdx]) = (array[minIdx], array[i]);
        }
    }
}

3. 插入排序

public class InsertionSorter : ISorter
{
    public void Sort(T[] array, IComparer comparer = null)
    {
        comparer ??= Comparer.Default;
        int n = array.Length;
        
        for (int i = 1; i < n; i++)
        {
            T key = array[i];
            int j = i - 1;
            
            while (j >= 0 && comparer.Compare(array[j], key) > 0)
            {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
}

4. 希爾排序

public class ShellSorter : ISorter
{
    public void Sort(T[] array, IComparer comparer = null)
    {
        comparer ??= Comparer.Default;
        int n = array.Length;
        
        // Knuth 序列: h = 3*h + 1
        int h = 1;
        while (h <= n / 3) h = 3 * h + 1;
        
        while (h > 0)
        {
            // h-排序（插入排序變體）
            for (int i = h; i < n; i++)
            {
                T key = array[i];
                int j = i;
                
                while (j >= h && comparer.Compare(array[j - h], key) > 0)
                {
                    array[j] = array[j - h];
                    j -= h;
                }
                array[j] = key;
            }
            h /= 3;
        }
    }
}

效能測試與驗證

public static class SortBenchmark
{
    public static void Run()
    {
        var algorithms = new (string Name, ISorter Sorter)[]
        {
            ("Bubble", new BubbleSorter()),
            ("Selection", new SelectionSorter()),
            ("Insertion", new InsertionSorter()),
            ("Shell", new ShellSorter()),
            ("Array.Sort", new BuiltInSorter())
        };

        int[] sizes = { 100, 1000, 5000 };
        var random = new Random(42);

        foreach (int size in sizes)
        {
            Console.WriteLine($"\n=== Array Size: {size} ===");
            int[] original = Enumerable.Range(0, size).Select(_ => random.Next(10000)).ToArray();
            
            foreach (var (name, sorter) in algorithms)
            {
                int[] copy = (int[])original.Clone();
                var sw = Stopwatch.StartNew();
                sorter.Sort(copy);
                sw.Stop();
                
                bool correct = copy.SequenceEqual(original.OrderBy(x => x));
                Console.WriteLine($"{name,-12}: {sw.ElapsedMilliseconds,6} ms  {(correct ? "✅" : "❌")}");
            }
        }
    }
}

class BuiltInSorter : ISorter
{
    public void Sort(T[] array, IComparer comparer = null) 
        => Array.Sort(array, comparer ?? Comparer.Default);
}

典型輸出結果（參考）

=== Array Size: 100 ===
Bubble      :      0 ms  ✅
Selection   :      0 ms  ✅
Insertion   :      0 ms  ✅
Shell       :      0 ms  ✅
Array.Sort  :      0 ms  ✅

=== Array Size: 1000 ===
Bubble      :     12 ms  ✅
Selection   :      3 ms  ✅
Insertion   :      1 ms  ✅
Shell       :      0 ms  ✅
Array.Sort  :      0 ms  ✅

=== Array Size: 5000 ===
Bubble      :    285 ms  ✅
Selection   :     72 ms  ✅
Insertion   :     18 ms  ✅
Shell       :      3 ms  ✅
Array.Sort  :      1 ms  ✅

實務選擇指南

• n < 50：插入排序（常數因子小、適應性好）
• 一般用途：直接用 Array.Sort / List.Sort（Timsort，O(n log n)、穩定、高度優化）
• 嵌入式/記憶體受限：希爾排序（原地、無遞迴、無額外記憶體）
• 平行處理：Array.Sort 內部已平行化（大陣列）

總結

理解經典排序演算法有助於面試與演算法思維訓練，但生產代碼請優先使用框架內建排序。若需客製化比較邏輯，實作 IComparer<T> 並傳入 Array.Sort(array, comparer) 即可獲得最佳效能與正確性。