演算法筆記：非遞迴排序法詳解（冒泡、插入、希爾）

前言

排序是資料處理的基石。上一篇比較了線性搜尋與二分搜尋的效能差距：百萬筆資料線性搜尋平均需 50 萬次比較，二分搜尋僅 20 次。既然排序能大幅提升查詢效能，本文系統整理三種經典非遞迴排序：冒泡排序、插入排序、希爾排序。遞迴排序（快速、歸並、堆積）留待下篇。

1. 冒泡排序

基本概念

每一輪將尚未排序區間中最大的元素「浮」到最右端。外層迴圈控制尚未排序的右邊界 outer，內層迴圈相鄰比較並交換。

基礎版

void bubble_sort(int array[], int length)
{
    if (array == NULL || length == 0) return;

    for (int outer = length - 1; outer >= 1; --outer) {
        for (int inner = 0; inner < outer; ++inner) {
            if (array[inner] > array[inner + 1]) {
                int tmp = array[inner];
                array[inner] = array[inner + 1];
                array[inner + 1] = tmp;
            }
        }
    }
}

優化：提前結束旗標

若某輪內層迴圈完全無交換，代表陣列已有序，可立即結束。

void bubble_sort_optimized(int array[], int length)
{
    if (array == NULL || length == 0) return;

    for (int outer = length - 1; outer >= 1; --outer) {
        int swapped = 0;
        for (int inner = 0; inner < outer; ++inner) {
            if (array[inner] > array[inner + 1]) {
                int tmp = array[inner];
                array[inner] = array[inner + 1];
                array[inner + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;   /* 提前結束 */
    }
}

2. 插入排序

核心思想

維護一個「已排序區間」與「未排序區間」。每次從未排序區間取出第一個元素，在已排序區間中由右向左比較，找到插入位置並平移元素。

實作

void insert_sort(int array[], int length)
{
    if (array == NULL || length == 0) return;

    for (int outer = 1; outer < length; ++outer) {
        int key = array[outer];
        int inner = outer - 1;
        while (inner >= 0 && array[inner] > key) {
            array[inner + 1] = array[inner];
            --inner;
        }
        array[inner + 1] = key;
    }
}

注意：插入排序無法像冒泡那樣用旗標提前結束，因為每輪皆為局部比較，無法判斷全域有序。

3. 希爾排序

動機

插入排序在資料「近乎有序」時極快（O(n)），但在逆序時退化為 O(n²)。希爾排序先以較大間距分組排序，使陣列宏觀有序，再逐步縮小間距，最後間距為 1 時即為插入排序，此時資料已近乎有序，效率大增。

間距序列

本文採用簡單的 step = length/2, length/4, ..., 1（原文示範 5, 3, 1），實務上常用 Sedgewick 或 Ciura 序列。

實作

void shell_sort(int array[], int length)
{
    if (array == NULL || length == 0) return;

    for (int gap = length / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < length; ++i) {
            int key = array[i];
            int j = i - gap;
            while (j >= 0 && array[j] > key) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = key;
        }
    }
}

總結與建議

• 三種演算法皆為原地排序，空間複雜度 O(1)。
• 冒泡排序教學價值大，實務極少用；插入排序適合小規模或近乎有序資料；希爾排序是中小型陣列的實用選擇。
• 撰寫排序程式時，邊界條件（長度 0、1、重複值）測試至關重要。
• 生產環境優先使用標準庫 qsort / std::sort，僅在嵌入式或教學場景手寫。