使用Java實現希爾排序算法

用Java實現希爾排序算法¶

一、什麼是希爾排序？¶

希爾排序（Shell Sort）是插入排序的一種改進版本。普通插入排序在數組接近有序時效率很高，但如果數組逆序，每次插入都需要大量移動操作。希爾排序通過分組插入的方式，先讓數組部分有序，最後再用插入排序完成整體排序，從而減少移動次數，提高效率。

二、核心思想¶

希爾排序的關鍵是引入“步長（Gap）”，將數組分成若干個子序列，對每個子序列進行插入排序。然後逐步縮小步長，重複分組和排序，直到步長爲1（此時等價於普通插入排序）。

分組：步長爲gap時，數組被分成gap個獨立的子序列，每個子序列的元素索引滿足i, i+gap, i+2gap...（如gap=2時，子序列爲[0,2,4], [1,3]）。
插入排序：對每個子序列單獨執行插入排序，使子序列有序。
縮小步長：步長從數組長度的一半開始，每次減半（gap = gap/2），直到gap=0。

三、算法步驟¶

初始化步長：gap = 數組長度 / 2。
分組插入排序：對每個子序列執行插入排序（遍歷每個元素，將其插入到子序列的正確位置）。
縮小步長：gap = gap / 2，重複步驟2，直到gap=0。

四、Java代碼實現¶

public class ShellSort {
    // 希爾排序主方法
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始步長爲數組長度的一半，逐步縮小
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 對每個分組執行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i]; // 臨時保存當前元素
                int j;
                // 向前比較並移動元素，找到插入位置
                for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
                    arr[j + gap] = arr[j]; // 元素後移
                }
                arr[j + gap] = temp; // 插入到正確位置
            }
        }
    }

    // 測試方法
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        System.out.println("排序前數組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        shellSort(arr);

        System.out.println("\n排序後數組：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

五、代碼解釋¶

外層循環：控制步長gap從n/2開始，每次減半，直到gap=0。
內層循環：遍歷每個分組的元素，對每個元素執行插入排序。
temp = arr[i]：臨時保存當前元素，避免移動時被覆蓋。
for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)：從當前元素的前一個元素開始，向左比較，若temp更小則後移元素。
arr[j + gap] = temp：將temp插入到最終找到的位置。

六、示例演示¶

以數組[12, 34, 54, 2, 3]爲例：
1. 初始步長：gap = 5/2 = 2，分組爲[12,54,3]和[34,2]。
- 對[12,54,3]排序：34和2交換後，數組變爲[3,2,12,34,54]。
2. 步長縮小：gap = 2/2 = 1，此時等價於普通插入排序，數組最終有序爲[2,3,12,34,54]。

七、總結¶

希爾排序通過分組減少移動次數和逐步有序化，比普通插入排序更高效。初學者可重點理解步長的作用和分組插入的邏輯，掌握後可進一步學習更復雜的步長序列（如3k+1）以優化性能。

輸出結果：

排序前數組：
12 34 54 2 3 
排序後數組：
2 3 12 34 54