Java 實現希爾排序：分組插入排序的高效改進

希爾排序：從插入排序到亞線性級效能的躍升

希爾排序（Shell Sort）通過預設間隔分組插入排序，將元素大步長移動至大致位置，再縮小間隔逐步有序。本文提供標準 Java 實現與間隙序列選擇建議。

算法核心思想

1. 選擇間隙序列 h（如 n/2, n/4, ..., 1）
2. 按間隙分組，對每組執行插入排序
3. 縮小間隙重複，直到 h=1 完成最終插入排序

標準實現

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {        // 間隙序列：n/2, n/4, ...
        for (int i = gap; i < n; i++) {                // 插入排序起始位置
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {  // 組內插入排序
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

間隙序列選擇影響效能

效能特徵

• 時間複雜度：取決於間隙序列，最優 O(n log² n)，最差 O(n²)
• 空間複雜度：O(1) 原地排序
• 穩定性：不穩定（長距離交換破壞相對順序）
• 適用場景：中等規模數據（萬級）、嵌入式環境（無遞歸棧、代碼極短）

對比基準

同等數據量下：希爾排序 ≫ 直接插入/選擇/冒泡，但 ≪ 快排/歸併/堆排。Java 內置 Arrays.sort()（雙軸快排+TimSort）生產環境首選。

1. 上一篇文章： AndEngine 實現菜單滑動效果：SurfaceScrollDetector + 雙向箭頭導航
2. 下一篇文章： Java 實現折半插入排序：二分查找優化插入位置

Java 相關知識

Java 多執行緒入門指南（7）：向執行緒傳遞資料的三種核心模式

背景：同步 vs 非同步資料流 傳統同步呼叫：result

設計模式精講：責任鏈模式——靈活替代 if-else 鏈的解耦利器

責任鏈模式讓多個對象都有機會處理請求，將請求發送者與接收者解

JNI 深度解析：Java 本地接口工作原理與類型映射全圖譜

為什麼需要 JNI？ Java 「一次編寫，到處運行」的代價

Java super 關鍵字深度解析：訪問父類字段、調用父類方法、構造器鏈、內存模型圖解

super 是 Java 中引用父類對象的關鍵字，配合 th