排序算法實戰：從冒泡到希爾排序的效能優化之路

排序算法實戰：從冒泡到希爾排序的效能優化之路

面對 N ≤ 10⁵ 規模整數排序，基礎 O(N²) 算法（冒泡、插入）在逆序、大量隨機數據下會超時。本文記錄從冒泡、插入到希爾排序的優化過程，並分析各測試數據特點對算法選擇的啟示。

一、題目需求與測試數據分析

• 輸入：N 及 N 個長整型整數。
• 輸出：升序序列，空格分隔，行尾無多餘空格。
• 測試點：

二、算法演進與代碼實現

1. 冒泡排序（優化版）

void Bubble_Sort(int *a, int n) {
    bool flag;
    for (int i = n-1; i > 0; i--) {
        flag = true;
        for (int j = 0; j < i; j++)
            if (a[j] > a[j+1]) { swap(a[j], a[j+1]); flag = false; }
        if (flag) break; // 本輪無交換，已有序
    }
}

測試點 4、6、8 超時（O(N²) 在 10⁵ 逆序/隨機過慢）。

2. 插入排序

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

測試點 6（逆序 10⁵）超時，近有序數據較快但最壞情況仍 O(N²)。

3. 希爾排序（原始增量序列）

void Shell_Sort(int *a, int n) {
    for (int gap = n/2; gap > 0; gap /= 2)
        for (int i = gap; i < n; i++) {
            int tmp = a[i], j;
            for (j = i; j >= gap && a[j-gap] > tmp; j -= gap)
                a[j] = a[j-gap];
            a[j] = tmp;
        }
}

全測試點通過。希爾排序平均 O(N¹·⁵)，對 10⁵ 規模極具優勢。

三、關鍵測試點針對性分析

• 數據 5（順序）：插入排序 O(N) 最快，希爾排序略慢但可接受。
• 數據 6（逆序）：冒泡/插入最壞 O(N²) 超時，希爾排序間隔跳躍大幅減少移動次數。
• 數據 7（近有序）：插入排序極快，希爾排序表現穩健。
• 數據 8（小範圍正整數 ≤1000）：計數排序 O(N+K) 最優，但希爾排序無需額外空間也能通過。

四、進階優化方向

1. 更優增量序列：Sedgewick、Tokuda 序列可將希爾排序提升至 O(N¹·²⁵) 甚至 O(N log²N)。
2. 混合策略：小區間（如 < 50）改用插入排序，大區間用希爾/快排。
3. 非比較排序：針對數據 8 可用計數排序/基數排序 O(N) 線性時間。

五、完整 AC 代碼

#include 
void Shell_Sort(int *a, int n) {
    for (int gap = n/2; gap > 0; gap /= 2)
        for (int i = gap; i < n; i++) {
            int tmp = a[i], j;
            for (j = i; j >= gap && a[j-gap] > tmp; j -= gap)
                a[j] = a[j-gap];
            a[j] = tmp;
        }
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
        if (i != n-1) printf(" "); else printf("\n");
    }
}
int main() {
    int N; scanf("%d", &N);
    int a[N];
    for (int i = 0; i < N; i++) scanf("%d", &a[i]);
    Shell_Sort(a, N);
    return 0;
}

六、總結

同一問題，算法選擇決定成敗。理解數據分布特徵，選擇合適時間複雜度算法，是競賽與工程優化的核心能力。希爾排序以極簡代碼實現了亞線性級效能，是中等規模排序的「性價比之王」。