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

前言

排序演算法是程式設計基礎。本文提供四種經典排序法的 C# 正確實作，修正原始碼片段中的語法錯誤，並補充效能測量與適用場景說明。

1. 氣泡排序

原理：相鄰元素兩兩比較，大者後移，每輪將最大值「浮」至末端。時間複雜度 O(n²)，穩定排序，適合教學或極小資料集。

public void BubbleSort(int[] list)
{
    long start = DateTime.Now.Ticks;
    int n = list.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (list[j] > list[j + 1])
            {
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
    long elapsed = DateTime.Now.Ticks - start;
    Console.WriteLine($"BubbleSort: {elapsed / 10000.0:F2} ms");
}

2. 選擇排序

原理：每輪從未排序區找最小值，放到已排序區末尾。同為 O(n²)，不穩定，但交換次數少（最多 n-1 次）。

public void SelectionSort(int[] list)
{
    long start = DateTime.Now.Ticks;
    int n = list.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (list[j] < list[minIdx]) minIdx = j;
        }
        if (minIdx != i)
        {
            int temp = list[i];
            list[i] = list[minIdx];
            list[minIdx] = temp;
        }
    }
    long elapsed = DateTime.Now.Ticks - start;
    Console.WriteLine($"SelectionSort: {elapsed / 10000.0:F2} ms");
}

3. 插入排序

原理：將未排序元素插入已排序序列適當位置。近似有序資料表現優異（最佳 O(n)），穩定，適合小規模或近乎有序資料。

public void InsertionSort(int[] list)
{
    long start = DateTime.Now.Ticks;
    for (int i = 1; i < list.Length; i++)
    {
        int key = list[i];
        int j = i - 1;
        while (j >= 0 && list[j] > key)
        {
            list[j + 1] = list[j];
            j--;
        }
        list[j + 1] = key;
    }
    long elapsed = DateTime.Now.Ticks - start;
    Console.WriteLine($"InsertionSort: {elapsed / 10000.0:F2} ms");
}

4. 希爾排序

原理：插入排序改良版，先按間距分組排序，逐步縮小間距至 1。時間複雜度介於 O(n log n) ~ O(n²) 間，不穩定，中等規模資料效能優於上述三種。

public void ShellSort(int[] list)
{
    long start = DateTime.Now.Ticks;
    int n = list.Length;
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        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;
        }
    }
    long elapsed = DateTime.Now.Ticks - start;
    Console.WriteLine($"ShellSort: {elapsed / 10000.0:F2} ms");
}

效能比較與選擇建議

實務建議： 實際專案請直接使用 Array.Sort() 或 List<T>.Sort()（內建 Introspective Sort，混合快速/堆積/插入排序），效能與穩健度遠優於手寫演算法。