Java 實作希爾排序演算法：增量序列最佳化與完整程式碼

ShellSort 類別完整實作

package Utils.Sort;

/**
 * 希爾排序，要求待排序陣列必須實作 Comparable 介面
 */
public class ShellSort implements SortStrategy {
    private int[] increment;

    /**
     * 利用希爾排序演算法對陣列 obj 進行排序
     */
    public void sort(Comparable[] obj) {
        if (obj == null) {
            throw new NullPointerException("The argument can not be null!");
        }
        // 初始化步長
        initGap(obj);
        // 步長依次變化（遞減）
        for (int i = increment.length - 1; i >= 0; i--) {
            int step = increment[i];
            // 由步長位置開始
            for (int j = step; j < obj.length; j++) {
                Comparable tmp;
                // 如果後面的小於前面的（相隔 step），則與前面交換
                for (int m = j; m >= step; m = m - step) {
                    if (obj[m].compareTo(obj[m - step]) < 0) {
                        tmp = obj[m - step];
                        obj[m - step] = obj[m];
                        obj[m] = tmp;
                    }
                    // 因為之前的位置必定已經比較過，所以這裡直接退出迴圈
                    else {
                        break;
                    }
                }
            }
        }
    }

    /**
     * 根據陣列長度確定求增量公式的最大指數
     * 公式：pow(4, i) - 3 * pow(2, i) + 1 和 9 * pow(4, i) - 9 * pow(2, i) + 1
     * @return int[] 兩個公式的最大指數
     * @param length 陣列長度
     */
    private int[] initExponent(int length) {
        int[] exp = new int[2];
        exp[0] = 1;
        exp[1] = -1;
        int[] gap = new int[2];
        gap[0] = gap[1] = 0;
        // 確定兩個公式的最大指數
        while (gap[0] < length) {
            exp[0]++;
            gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
        }
        exp[0]--;
        while (gap[1] < length) {
            exp[1]++;
            gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
        }
        exp[1]--;
        return exp;
    }

    private void initGap(Comparable[] obj) {
        // 利用公式初始化增量序列
        int exp[] = initExponent(obj.length);
        int[] gap = new int[2];
        increment = new int[exp[0] + exp[1]];
        // 將增量陣列由大到小賦值
        for (int i = exp[0] + exp[1] - 1; i >= 0; i--) {
            gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
            gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
            // 將大的增量先放入增量陣列，這裡實際上是一個歸併排序
            // 不需要考慮 gap[0] == gap[1] 的情況，因為不可能出現相等
            if (gap[0] > gap[1]) {
                increment[i] = gap[0];
                exp[0]--;
            } else {
                increment[i] = gap[1];
                exp[1]--;
            }
        }
    }
}

演算法核心解析

• 介面需求： 待排序陣列元素須實作 Comparable
• 增量序列： 採用兩個數學公式產生的序列合併（歸併式由大到小），而非單純 n/2 遞減，效能更優
• 插入排序變體： 每個步長下執行類似插入排序的比較交換，遇已排序段提前 break 優化
• 時間複雜度： 依增量序列而定，典型 O(n^1.5) 至 O(n log²n)

關鍵設計亮點

1. 雙公式增量序列： 4i - 3×2i + 1 與 9×4i - 9×2i + 1，覆蓋更優間距分佈
2. 歸併式增量排序： initGap 中將兩序列由大到小合併，避免重複計算
3. 提前終止優化： 內層迴圈 else break 利用已排序特性減少比較次數
4. 策略模式： 實作 SortStrategy 介面，便於擴展替換