C語言希爾排序常見錯誤分析：分組插入邏輯缺失導致局部無序

問題代碼回顧

開發者根據希爾排序思想編寫代碼，但發現每次排序結果總有一個數字位置錯誤，其餘有序。核心片段如下：

void xishu(int a[], int n) {
    int i, j;
    int d = n / 2;
    while (d > 0) {
        for (j = 0, i = d; i < n; i++, j++) {
            if (a[i] < a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        d = d / 2;
    }
}

錯誤根因：僅進行單次比較交換，缺失分組內插入排序邏輯

希爾排序的核心是「分組進行插入排序」。當增量 d=2 時，數組被分為 2 組（下標 0,2,4... 和 1,3,5...），每組內部需完整執行插入排序，而非僅比較相距 d 的兩個元素交換一次。原代碼的 for 循環相當於只做了一趟「冒泡式」交換，無法保證組內有序。

正確實現：分組插入排序

void shellSort(int a[], int n) {
    for (int d = n / 2; d > 0; d /= 2) {
        // 對每組進行插入排序
        for (int i = d; i < n; i++) {
            int temp = a[i];
            int j;
            // 組內插入：從 i-d, i-2d... 向前查找插入位置
            for (j = i - d; j >= 0 && a[j] > temp; j -= d) {
                a[j + d] = a[j]; // 後移
            }
            a[j + d] = temp; // 插入
        }
    }
}

關鍵差異對比

調試建議

• 打印每輪增量 d 後的數組狀態，觀察分組變化。
• 以 d=1 時退化為普通插入排序作為驗證基準。
• 測試用例：已有序、逆序、重複元素、單元素數組。

總結

希爾排序 ≠ 間隔交換。其本質是分組插入排序，必須在內層循環中完整實現插入邏輯（後移+插入），才能保證全局有序。初學者常忽略「組內多次比較後移」步驟，導致局部無序。