C# 演算法實戰：希爾排序原理、實作與效能分析

前言：為何需要希爾排序？

插入排序在「近乎有序」的資料上表現極佳（O(n)），但在逆序資料上退化為 O(n²)。希爾排序（Shell Sort）由 Donald Shell 於 1959 年提出，核心思想是分組插入排序：先讓距離較遠的元素直接交換，逐步縮小間距，最終以間距 1 完成普通插入排序。此「預排序」策略大幅減少元素移動次數。

演算法核心邏輯

1. 選擇增量序列（Gap Sequence），常用 1, 4, 13, 40, 121...（h = 3*h + 1）
2. 對每個增量 h，將陣列分為 h 組，各組獨立進行插入排序
3. 遞減增量，重複步驟 2，直到 h = 1

C# 標準實作

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

        int n = array.Length;
        // 計算初始增量：Knuth 序列 (h = 3*h + 1) 且 h < n/3
        int h = 1;
        while (h < n / 3) h = 3 * h + 1; // 1, 4, 13, 40, ...

        for (; h > 0; h /= 3)
        {
            // 對每個分組進行插入排序
            for (int i = h; i < n; i++)
            {
                int temp = array[i];
                int j = i;
                // 向前比較、位移，步長為 h
                while (j >= h && array[j - h] > temp)
                {
                    array[j] = array[j - h];
                    j -= h;
                }
                array[j] = temp;
            }
        }
    }
}

測試驗證

var arr = new[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
Console.WriteLine("排序前: " + string.Join(", ", arr));
ShellSort.Sort(arr);
Console.WriteLine("排序後: " + string.Join(", ", arr));
// 輸出: 1, 2, 3, 5, 6, 9, 10, 12, 33, 34, 47, 55, 75, 87

增量序列的選擇與效能影響

進階挑戰：實作泛型與介面化

原始碼僅支援 int[]。若要支援任意可比較型別，可引入 IComparable<T> 並採用策略模式：

public interface ISorter where T : IComparable
{
    void Sort(T[] array);
}

public class ShellSorter : ISorter where T : IComparable
{
    public void Sort(T[] array)
    {
        int n = array.Length;
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;

        for (; h > 0; h /= 3)
        {
            for (int i = h; i < n; i++)
            {
                T temp = array[i];
                int j = i;
                while (j >= h && array[j - h].CompareTo(temp) > 0)
                {
                    array[j] = array[j - h];
                    j -= h;
                }
                array[j] = temp;
            }
        }
    }
}

如此即可排序 string[]、DateTime[] 或任何實作 IComparable<T> 的型別。

效能基準測試（參考）

// 100,000 筆隨機整數
var data = Enumerable.Range(0, 100000).OrderBy(_ => Guid.NewGuid()).ToArray();

var sw = Stopwatch.StartNew();
ShellSort.Sort(data);
sw.Stop();
Console.WriteLine($"Shell Sort: {sw.ElapsedMilliseconds} ms");
// 典型結果：~15-30 ms (視 CPU 而定)
// 對比：Array.Sort (Introsort) ~5-10 ms

總結

希爾排序是「簡單排序」向「高效排序」跨越的關鍵橋樑。它以 O(1) 空間複雜度、相對簡單的程式碼，達到 O(N^{3/2}) 甚至更好的時間複雜度，適合中小型資料集或嵌入式環境。理解其分組預排序思想，有助於掌握後續進階演算法（如梳狀排序、快速排序分區邏輯）的設計精髓。