C# 經典排序算法實作：希爾排序

算法原理

希爾排序是插入排序的改進版，將陣列按間距分組進行插入排序，間距逐漸縮小至 1。時間複雜度介於 O(n log n) 到 O(n²) 之間，視間距序列而定，不穩定排序。

C# 實作

using System;

public class ShellSorter
{
    public void Sort(int[] list)
    {
        int inc;
        // 計算初始間距 (Knuth 序列: 1, 4, 13, 40...)
        for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
        
        for (; inc > 0; inc /= 3)
        {
            for (int i = inc; i < list.Length; i += inc)
            {
                int temp = list[i];
                int j = i;
                while (j >= inc && list[j - inc] > temp)
                {
                    list[j] = list[j - inc];
                    j -= inc;
                }
                list[j] = temp;
            }
        }
    }
}

// 測試
public class Program
{
    public static void Main()
    {
        int[] arr = { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
        new ShellSorter().Sort(arr);
        Console.WriteLine(string.Join(" ", arr));
    }
}

間距序列選擇

結語

希爾排序是中小型資料集的優秀選擇，實作簡單且無需額外記憶體。大規模資料建議改用快速排序、合併排序或 .NET 內建 Array.Sort (Introsort)。