希爾排序（Shell Sort）C++ 實現與原理詳解

算法原理

希爾排序是插入排序的改進版，通過分組進行間隔插入排序，逐步縮小間隔（增量序列），最終間隔為 1 時完成整體有序。常用增量序列為 n/2, n/4, ..., 1。

C++ 實現代碼

#include <iostream>
using namespace std;

// 希爾排序（升序）
void ShellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = a[i];
            int j;
            for (j = i - gap; j >= 0 && temp < a[j]; j -= gap) {
                a[j + gap] = a[j];
            }
            a[j + gap] = temp;
        }
    }
}

// 列印陣列
void PrintArray(int a[], int n) {
    for (int i = 0; i < n; ++i)
        cout << a[i] << ' ';
    cout << endl;
}

int main() {
    int a[9] = {7, 3, 5, 8, 9, 1, 2, 4, 6};
    ShellSort(a, 9);
    PrintArray(a, 9);  // 輸出: 1 2 3 4 5 6 7 8 9
    return 0;
}

關鍵點

• 時間複雜度：取決於增量序列，常見序列為 O(n²)，最佳序列可達 O(n log² n)。
• 空間複雜度：O(1)，原地排序。
• 不穩定排序：相同元素相對順序可能改變。
• 適用場景：中小型資料集，實現簡單且效率優於簡單插入排序。

優化建議

1. 使用更優增量序列（如 Sedgewick、Ciura 序列）。
2. 對於極小陣列（< 50），直接插入排序可能更快。
3. 模板化支援任意可比較型別與隨機存取迭代器。