資料結構經典演算法：C# 實作希爾排序法

希爾排序為分組插入排序改良版，縮小增量序列逐步有序化：

using System;

namespace ShellSorter {
    public class ShellSorter {
        public void Sort(int[] list) {
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3) {
                for (int i = inc + 1; i <= list.Length; i += inc) {
                    int t = list[i - 1];
                    int j = i;
                    while (j > inc && list[j - inc - 1] > t) {
                        list[j - 1] = list[j - inc - 1];
                        j -= inc;
                    }
                    list[j - 1] = t;
                }
            }
        }
    }

    public class MainClass {
        public static void Main() {
            int[] arr = {1,5,13,6,10,55,99,2,87,12,34,75,33,47};
            var sorter = new ShellSorter();
            sorter.Sort(arr);
            foreach (var n in arr) Console.Write("{0} ", n);
            Console.WriteLine();
        }
    }
}

增量序列採用 Knuth 建議 1, 4, 13, 40... (3k+1)，平均時間複雜度 O(n^1.5)，優於單純插入排序。