插入排序與希爾排序：原理、代碼實現、時間複雜度深度分析

一、插入排序

核心思想

將陣列分為「已排序區」與「未排序區」。初始已排序區僅含首元素。每輪從未排序區取出首元素 key，在已排序區從右向左掃描，將大於 key 的元素右移，騰出位置插入 key。類似撲克牌整理手牌。

動圖演示

C 語言實現

void InsertSort(int *A, int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = A[i];
        for (j = i; j > 0 && key < A[j-1]; j--) {
            A[j] = A[j-1]; // 右移
        }
        A[j] = key;
    }
}

時間複雜度分析

逆序對視角的平均複雜度證明

1. 定義逆序對：i < j 且 A[i] > A[j]。
2. 插入排序本質是「交換相鄰元素消除逆序對」，總操作次數 = 逆序對數 + O(N)。
3. 任意含 N 個互異元素的排列，其逆序對數期望 = N(N-1)/4。
   證明：對任意序列 A，其反序列 A'。任意元素對 (x,y) 必在 A 或 A' 中構成逆序對。總對數 C(N,2)=N(N-1)/2，故 A 平均逆序對 = 一半 = N(N-1)/4。
4. 故平均時間 O(N²)。

適用場景

• 資料量小（< 50）
• 資料近乎有序（如線上插入新元素）
• 作為快速排序、歸併排序的小區間基礎排序（閾值 16~32）

二、希爾排序

核心改進

插入排序只比較相鄰元素，移動代價大。希爾排序引入增量序列 h₁, h₂, ..., hₖ=1，每輪按增量 h 分組進行插入排序，使元素大步長移動，最後一輪 h=1 即普通插入排序，但此時陣列已近乎有序，極快。

增量序列選擇與複雜度

C 語言實現（Shell 原始增量）

void ShellSort(int *A, int n) {
    int i, j, inc, key;
    for (inc = n/2; inc > 0; inc /= 2) {
        for (i = inc; i < n; i++) {
            key = A[i];
            for (j = i; j >= inc && key < A[j-inc]; j -= inc) {
                A[j] = A[j-inc];
            }
            A[j] = key;
        }
    }
}

關鍵性質

• 每輪 h-排序後，陣列滿足 A[i] <= A[i+h]，稱為 h-有序。
• 後續更小增量排序保持已建立的 h-有序性。
• 非穩定排序（長距離交換可能改變相等元素相對順序）。

總結對比