非遞歸排序算法深度解析：冒泡、插入、希爾排序的原理、優化與工程實踐

前言

排序是將無序序列轉為有序的基本運算。上一篇證明了有序數據配合二分查找可將 O(n) 降為 O(log n)，這正是排序的核心價值。本文聚焦非遞歸 (迭代) 排序三大經典——冒泡、插入、希爾排序，從底層邏輯到代碼細節，從基礎版到優化版，構建可直接落地的工程級認知。

一、冒泡排序：以鄰交換推大元素「冒泡」至尾部

核心邏輯

外層控制無序區右邊界 outer 從 n-1 遞減至 1；內層 inner 從 0 遍歷至 outer-1，相鄰比較交換，最大元素逐輪沉底。

基礎版

void bubble_sort(int arr[], int n) {
    if (!arr || n <= 1) return;
    for (int outer = n - 1; outer >= 1; outer--) {
        for (int inner = 0; inner < outer; inner++) {
            if (arr[inner] > arr[inner + 1]) {
                int tmp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = tmp;
            }
        }
    }
}

優化版：早退標記

若某輪遍歷無任何交換，說明已有序，立即終止。最好情況 (已有序) 從 O(n²) 降為 O(n)。

void bubble_sort_opt(int arr[], int n) {
    if (!arr || n <= 1) return;
    for (int outer = n - 1; outer >= 1; outer--) {
        int swapped = 0;
        for (int inner = 0; inner < outer; inner++) {
            if (arr[inner] > arr[inner + 1]) {
                int tmp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 關鍵優化
    }
}

複雜度與特性

二、插入排序：構建有序區，逐個插入新元素

核心邏輯

維護 [0, outer-1] 為有序區。外層 outer 從 1 到 n-1，將 arr[outer] 向左比較移位，找到插入點。

標準實現

void insert_sort(int arr[], int n) {
    if (!arr || n <= 1) return;
    for (int outer = 1; outer < n; outer++) {
        int key = arr[outer];
        int inner = outer - 1;
        // 向右移動大於 key 的元素
        while (inner >= 0 && arr[inner] > key) {
            arr[inner + 1] = arr[inner];
            inner--;
        }
        arr[inner + 1] = key; // 插入
    }
}

為何無「早退」優化？

插入排序每輪只處理局部有序區，即使某輪無移動，後續元素仍可能破壞有序性，無法像冒泡那樣全局判斷。但對近乎有序數據極其高效 (接近 O(n))。

複雜度與特性

三、希爾排序：插入排序的「間隔」增強版

核心思想

按遞減增量序列 (如 n/2, n/4, ..., 1 或 Knuth 序列 1, 4, 13, 40...) 分組，對每組執行插入排序。大步長快速移動元素接近最終位置，最後步長 1 時數組基本有序，插入排序極快。

實現 (Shell 原始增量序列)

void shell_sort(int arr[], int n) {
    if (!arr || n <= 1) return;
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        // 對每個分組做插入排序
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }
}

增量序列選擇影響性能

• Shell 原版 (n/2^k)：最壞 O(n²)，平均 ~O(n^1.5)
• Knuth ((3^k - 1)/2)：平均 O(n^1.25)
• Sedgewick / Ciura 序列：實測最優，接近 O(n log n)

複雜度與特性

四、三大算法綜合對比與選型指南

五、工程落地檢查清單

1. 邊界測試：空指針、長度 0/1、已有序、逆序、重複元素。
2. 穩定性驗證：定義結構體含 key 和 id，排序後檢查相同 key 的 id 相對順序。
3. 性能基準：使用 clock_gettime 或 std::chrono 測量不同規模 (100, 1000, 10000) 隨機/有序/逆序數據耗時。
4. 生產代碼原則：優先使用標準庫 qsort/std::sort/std::stable_sort (Introsort 混合快排/堆排/插入，O(n log n) 最壞保證)。手寫排序僅用於教學、特殊約束 (如嵌入式無 STL) 或面試。

結語

非遞歸排序雖時間復雜度多為 O(n²)，但理解其局部有序構建、元素移動最小化、間隔分治等核心思想，是掌握快速排序、歸併排序、堆排序等 O(n log n) 進階算法的基石。下一篇將深入遞歸排序殿堂——快速排序。