Java 實作 Shell Sort（希爾排序）完整範例與解析

希爾排序簡介

希爾排序是插入排序的改進版，通過分組插入排序逐步縮小增量（gap），最終在增量為 1 時完成普通插入排序。它是不穩定排序，平均時間複雜度取決於增量序列選擇，常見為 O(n^1.3) 到 O(n²) 之間。

核心邏輯

1. 選擇增量序列（如 gap = length/2，每輪折半）。
2. 按增量將數組分為若干子序列，對每組進行直接插入排序。
3. 縮小增量重複上述過程，直到 gap = 1 完成最後一次插入排序。

Java 完整實現

public class ShellSortDemo {
    public static void main(String[] args) {
        int[] arr = {44, 33, 99, 10, 30, 20, 59, 78, 23, 48};
        System.out.print("排序前：");
        printArray(arr);
        
        shellSort(arr);
        
        System.out.print("排序後：");
        printArray(arr);
    }
    
    private static void shellSort(int[] arr) {
        int len = arr.length;
        // 增量序列：每次折半
        for (int gap = len >> 1; gap > 0; gap >>= 1) {
            // 對每個分組進行直接插入排序
            for (int i = gap; i < len; i++) {
                int temp = arr[i];
                int j;
                // 組內插入排序：向前比較 gap 步長
                for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - gap]; // 後移元素
                }
                arr[j] = temp; // 插入正確位置
            }
        }
    }
    
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

關鍵點解析

為何使用 temp 暫存？

直接插入排序的核心是尋找插入位置，需將待插入元素暫存，騰出空位供後移操作。

內層循環條件 j >= gap && temp < arr[j - gap]

• j >= gap：確保不越界（組內第一個元素無需比較）。
• temp < arr[j - gap]：因組內已有序，找到合適位置即停止。

增量序列的選擇

本例採用 gap = length/2 折半序列（Shell 原始方案）。其他優化序列如 Hibbard、Sedgewick 可進一步降低時間複雜度，但實現較複雜。最後一次增量必須為 1 才能保證完全有序。

執行結果

排序前：44 33 99 10 30 20 59 78 23 48 
排序後：10 20 23 30 33 44 48 59 78 99 

總結

希爾排序通過預排序大幅減少元素移動次數，適合中等規模數據。理解「分組插入」與「增量縮小」的雙重循環結構是掌握該算法的關鍵。