C# 排序算法大全：冒泡、選擇、插入、希爾與快速排序完整實作與效能分析

前言：為什麼仍需掌握經典排序算法？

雖然 .NET 內建 Array.Sort 與 List<T>.Sort 已經高度優化（基於 Introspective Sort：快速排序 + 堆積排序 + 插入排序混合），但在以下情境理解經典算法至關重要：

• 面試與電腦科學基礎考核
• 特定資料結構或約束條件下的客製化排序
• 教學與算法思維訓練
• 效能調優時的決策依據

五大經典排序算法比較表

1. 冒泡排序——最直觀的交換排序

核心思想

重複遍歷陣列，比較相鄰元素，若順序錯誤則交換。每一輪將最大元素「冒泡」到末端。優化版加入旗標，若某輪無交換則提前結束。

C# 實作

public class BubbleSorter
{
    /// 

    /// 優化版冒泡排序：加入 early-exit 機制
    /// 
    public void Sort(int[] list)
    {
        if (list == null || list.Length <= 1) return;

        bool swapped;
        for (int i = 0; i < list.Length - 1; i++)
        {
            swapped = false;
            // 每輪減少一個已排序的尾部元素
            for (int j = 0; j < list.Length - 1 - i; j++)
            {
                if (list[j] > list[j + 1])
                {
                    Swap(list, j, j + 1);
                    swapped = true;
                }
            }
            // 本輪無交換，代表已有序
            if (!swapped) break;
        }
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2. 選擇排序——最小交換次數的選擇

核心思想

每輪從未排序區間選出最小元素，與未排序區間首位交換。無論資料分佈如何，交換次數固定為 O(n)，適合「寫入成本高」的儲存介質。

C# 實作

public class SelectionSorter
{
    public void Sort(int[] list)
    {
        if (list == null || list.Length <= 1) return;

        for (int i = 0; i < list.Length - 1; i++)
        {
            int minIndex = i;
            // 尋找未排序區間的最小值索引
            for (int j = i + 1; j < list.Length; j++)
            {
                if (list[j] < list[minIndex])
                    minIndex = j;
            }
            // 僅在必要時交換
            if (minIndex != i)
                Swap(list, i, minIndex);
        }
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. 插入排序——近乎有序資料的王者

核心思想

維護一個已排序的前綴區間，將下一個元素「插入」到正確位置。類似整理撲克牌。最佳情況 O(n)，是小規模或近乎有序資料的首選。

C# 實作

public class InsertionSorter
{
    public void Sort(int[] list)
    {
        if (list == null || list.Length <= 1) return;

        for (int i = 1; i < list.Length; i++)
        {
            int key = list[i];
            int j = i - 1;

            // 將大於 key 的元素向右位移
            while (j >= 0 && list[j] > key)
            {
                list[j + 1] = list[j];
                j--;
            }
            list[j + 1] = key;
        }
    }
}

4. 希爾排序——插入排序的高效改良

核心思想

將陣列按間隔分組，對每組進行插入排序，逐步縮小間隔至 1。利用插入排序對「近乎有序」資料高效的特性，大幅減少元素移動次數。間隔序列選擇影響效能，常用 Knuth 序列 (h = 3h + 1)。

C# 實作

public class ShellSorter
{
    public void Sort(int[] list)
    {
        if (list == null || list.Length <= 1) return;

        int n = list.Length;
        // 計算初始間隔 (Knuth 序列: 1, 4, 13, 40, 121...)
        int gap = 1;
        while (gap <= n / 3)
            gap = gap * 3 + 1;

        // 逐步縮小間隔
        while (gap > 0)
        {
            // 對每個間隔分組進行插入排序
            for (int i = gap; i < n; i++)
            {
                int temp = list[i];
                int j = i;
                while (j >= gap && list[j - gap] > temp)
                {
                    list[j] = list[j - gap];
                    j -= gap;
                }
                list[j] = temp;
            }
            gap = (gap - 1) / 3; // 反向縮小間隔
        }
    }
}

5. 快速排序——實務中最快的通用排序

核心思想

分治法：選擇基準值，將陣列分割為「小於基準」與「大於基準」兩個子陣列，遞迴排序。原地排序、快取友善、平均 O(n log n)。

關鍵優化點

• 基準值選擇：三數取中法避免最差情況
• 小陣列切換插入排序：閾值通常 10~20
• 尾遞迴優化：減少堆疊深度
• 三向切分：處理大量重複鍵值

C# 完整實作（含優化）

public class QuickSorter
{
    private const int InsertionSortThreshold = 16;

    public void Sort(int[] array)
    {
        if (array == null || array.Length <= 1) return;
        QuickSort(array, 0, array.Length - 1);
    }

    private void QuickSort(int[] arr, int low, int high)
    {
        // 小陣列改用插入排序
        if (high - low < InsertionSortThreshold)
        {
            InsertionSort(arr, low, high);
            return;
        }

        // 三數取中法選擇基準值
        int pivotIndex = MedianOfThree(arr, low, high);
        Swap(arr, pivotIndex, high); // 基準值移到末尾
        int pivot = arr[high];

        // 分割
        int left = low;
        int right = high - 1;

        while (left <= right)
        {
            while (left <= right && arr[left] < pivot) left++;
            while (left <= right && arr[right] > pivot) right--;
            if (left <= right)
            {
                Swap(arr, left, right);
                left++;
                right--;
            }
        }

        // 將基準值放回正確位置
        Swap(arr, left, high);

        // 尾遞迴優化：先排較小的分割
        if (left - low < high - left)
        {
            QuickSort(arr, low, left - 1);
            QuickSort(arr, left + 1, high);
        }
        else
        {
            QuickSort(arr, left + 1, high);
            QuickSort(arr, low, left - 1);
        }
    }

    private int MedianOfThree(int[] arr, int low, int high)
    {
        int mid = low + (high - low) / 2;
        if (arr[low] > arr[mid]) Swap(arr, low, mid);
        if (arr[low] > arr[high]) Swap(arr, low, high);
        if (arr[mid] > arr[high]) Swap(arr, mid, high);
        return mid;
    }

    private void InsertionSort(int[] arr, int low, int high)
    {
        for (int i = low + 1; i <= high; i++)
        {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

實測效能比較（參考數據）

測試環境：Intel i7-12700K, .NET 8, Release 模式，陣列長度 10,000，隨機整數

統一測試程式碼

class Program
{
    static void Main()
    {
        int[] testData = { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
        
        Console.WriteLine("原始資料: " + string.Join(", ", testData));
        
        var algorithms = new (string Name, Action Sort)[]
        {
            ("冒泡排序", arr => new BubbleSorter().Sort(arr)),
            ("選擇排序", arr => new SelectionSorter().Sort(arr)),
            ("插入排序", arr => new InsertionSorter().Sort(arr)),
            ("希爾排序", arr => new ShellSorter().Sort(arr)),
            ("快速排序", arr => new QuickSorter().Sort(arr)),
        };

        foreach (var (name, sort) in algorithms)
        {
            int[] copy = (int[])testData.Clone();
            var sw = System.Diagnostics.Stopwatch.StartNew();
            sort(copy);
            sw.Stop();
            Console.WriteLine($"{name}: {string.Join(", ", copy)} (耗時: {sw.ElapsedTicks} ticks)");
        }
    }
}

總結與選擇指南

• 生產環境：直接使用 Array.Sort / List<T>.Sort / LINQ OrderBy
• 教學/面試：掌握五大算法核心邏輯、複雜度分析、穩定性差異
• 客製化需求：理解快速排序分割邏輯、希爾排序間隔序列、插入排序適用場景
• 嵌入式/記憶體受限：希爾排序或優化版快速排序（原地、低空間複雜度）

延伸閱讀：.NET 內建排序實作原理 (Introspective Sort) | 平行排序 | 外部排序處理海量資料