Java 排序算法總結：希爾排序（縮小增量排序）詳解

希爾排序基本原理

希爾排序是插入排序的改進版，又稱「縮小增量排序」。它先選取一個小於數組長度的增量 gap，將數組分為若干子序列（間隔 gap 的元素分為一組），對每組進行直接插入排序。隨後逐漸縮小 gap（常用 gap = gap / 2），重複上述過程，直到 gap = 1 進行最後一次插入排序，此時數組基本有序，效率極高。

算法特性

• 時間複雜度：取決於增量序列，常見 O(n¹·⁵) ~ O(n²)，最壞 O(n²)。
• 空間複雜度：O(1)，原地排序。
• 穩定性：不穩定，相同元素可能因跨組移動而改變相對順序。
• 優勢：對中等規模數據表現優於 O(n²) 算法，代碼簡單，無需遞歸棧。

Java 完整實現

public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        // 增量序列：n/2, n/4, ..., 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 對每個子序列進行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i - gap;
                // 組內插入排序
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
            // 可選：打印每輪排序後狀態
            // System.out.println("gap=" + gap + ": " + Arrays.toString(arr));
        }
    }
}

增量序列選擇

原始 Shell 序列（n/2^k）並非最優。常用改進序列：

• Hibbard：2^k - 1（1, 3, 7, 15...），最壞 O(n¹·⁵)。
• Sedgewick：9·4^k - 9·2^k + 1 等，最壞 O(n⁴ᐟ³)。
• Ciura：經驗最優序列 {1, 4, 10, 23, 57, 132, 301, 701...}。

適用場景

希爾排序適合中等規模數據（數千~數萬），且對內存敏感的嵌入式環境。在 Java 中，Arrays.sort() 對基本類型使用雙軸快速排序，對對象數組使用 TimSort（歸併+插入），希爾排序多用於教學或特定約束場景。