使用C++實現希爾排序算法

什麼是希爾排序？¶

希爾排序（Shell Sort）是插入排序的一種改進版本，也稱爲“縮小增量排序”。它通過將數組分成多個子序列，對每個子序列進行插入排序，然後逐步縮小增量，直到增量爲1時完成整個數組的排序。這種方法的核心思想是讓數組中的元素更快地“移動”到正確的位置，從而減少插入排序的移動次數。

希爾排序的基本思路¶

分組：選擇一個增量（gap），將數組分成若干個子序列，每個子序列中的元素是相隔gap距離的元素。例如，若數組長度爲5，初始增量gap=2，則子序列爲[arr[0], arr[2], arr[4]]和[arr[1], arr[3]]。
子序列排序：對每個子序列進行直接插入排序。
縮小增量：將增量gap縮小（通常每次減半，如gap = gap/2），重複步驟1和2，直到gap=1。
最終排序：當gap=1時，整個數組已基本有序，此時只需進行一次完整的插入排序即可完成最終排序。

爲什麼要縮小增量？¶

初始大增量時，數組被分成較少的子序列，每個子序列較長，插入排序的移動次數少。
隨着增量減小，子序列逐漸合併，數組逐漸接近有序，最終只需少量移動即可完成排序。

排序過程示例¶

以數組[12, 34, 54, 2, 3]爲例，初始長度n=5，增量gap初始爲5/2=2：

第一次分組（gap=2）：
- 子序列1：[12, 54, 3]（索引0,2,4）
- 子序列2：[34, 2]（索引1,3）
- 對每個子序列插入排序後，數組變爲[12, 2, 54, 34, 3]。
縮小增量（gap=1）：
- 此時數組已基本有序，直接進行一次插入排序：
- 處理3時，與前面元素54、34、12比較，最終插入到索引0，數組變爲[3, 2, 12, 34, 54]。
- 處理2時，與3比較，插入到索引1，數組變爲[2, 3, 12, 34, 54]。

最終排序結果：[2, 3, 12, 34, 54]。

C++代碼實現¶

#include <iostream>
using namespace std;

// 希爾排序函數
void shellSort(int arr[], int n) {
    // 從大到小設置增量，初始爲n/2，每次減半直到gap=0
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 對每個gap分組中的元素進行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i]; // 當前待插入的元素
            int j;
            // 從當前元素開始，向前比較並移動元素
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap]; // 元素後移
            }
            arr[j] = temp; // 插入temp到正確位置
        }
    }
}

// 打印數組函數
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前數組：";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "排序後數組：";
    printArray(arr, n);

    return 0;
}

代碼解釋¶

外層循環（gap控制）：gap從n/2開始，每次減半，直到gap=0。
中層循環（分組插入排序）：對每個gap，從索引gap開始遍歷數組，將每個元素arr[i]視爲待插入元素。
內層循環（移動元素）：從i開始向前比較，若前一個元素（arr[j - gap]）大於當前元素（temp），則將前一個元素後移gap位，直到找到插入位置j，最後插入temp。

時間複雜度與空間複雜度¶

時間複雜度：平均爲O(n^1.3)（依賴增量選擇），最壞爲O(n^2)。
空間複雜度：O(1)（僅需臨時變量temp）。
穩定性：不穩定（分組插入排序可能改變相等元素的相對順序）。

總結¶

希爾排序通過分組和縮小增量的方式，有效減少了插入排序的移動次數，在數組較大時比普通插入排序更高效。初學者只需理解“分組→排序→縮小增量→最終排序”的核心邏輯，即可掌握其實現原理。