插入排序與希爾排序：C 實現與遞推邏輯解析

一、插入排序

維護前 k-1 有序，插入第 k 個元素。兩種掃描方向：

• 左→右：找首個 ≥ a[k]，插前面。
• 右→左（代碼採用）：找首個 ≤ a[k]，插後面，元素右移。

代碼

void InsertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int tmp = a[i], j = i - 1;
        while (j >= 0 && a[j] > tmp) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = tmp;
    }
}

二、希爾排序

分組插入排序，步長 gap = n/2, n/4, ..., 1。每組獨立插入排序，最後 gap=1 為全量插入排序。

代碼

void ShellSort(int a[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int k = 0; k < gap; k++) { // 每組
            for (int i = k+gap; i < n; i += gap) {
                int tmp = a[i], j = i - gap;
                while (j >= 0 && a[j] > tmp) {
                    a[j+gap] = a[j];
                    j -= gap;
                }
                a[j+gap] = tmp;
            }
        }
    }
}

複雜度對比

關鍵點

• 插入排序適合小規模/近乎有序數組。
• 希爾排序是插入排序的改進，步長序列影響性能（Hibbard, Sedgewick 序列更優）。
• 兩者皆為原地排序，代碼簡短，適合嵌入式/教學。