排序算法：希爾排序 Java 實現

希爾排序由 Donald Shell 於 1959 年發表，是插入排序的高效改進版本。

基本思想

1. 取增量 d1 < n，將記錄分組，距離為 d1 倍數的歸為一組。
2. 各組內進行直接插入排序。
3. 取更小增量 d2 < d1 重複分組排序。
4. 直至增量 dt = 1，所有記錄在一組中直接插入排序結束。

算法實現

public class ShellSorter {
    public void sort(int[] array) {
        int d = array.length;
        do {
            d /= 2;
            shellPass(array, d);
        } while (d > 1);
    }

    private void shellPass(int[] array, int d) {
        for (int i = d; i < array.length; i++) {
            int tmp = array[i];
            if (array[i] < array[i - d]) {
                int j;
                for (j = i - d; j >= 0 && tmp < array[j]; j -= d) {
                    array[j + d] = array[j];
                }
                array[j + d] = tmp;
            }
        }
    }
}

參考資料

1. 維基百科：希爾排序