經典 O(n²) 排序算法深度解析：冒泡、選擇、插入與希爾排序

O(n²) 級排序算法全景解析

雖然 O(n²) 時間複雜度的排序算法在大數據量場景下不具備實用性，但它們是理解排序核心思想、掌握算法分析方法的最佳入門教材。本文系統梳理冒泡、選擇、插入、希爾四大經典算法，從原理到優化，層層遞進。

一、冒泡排序：以鄰為伴，大者沉底

核心原理

1. 比較相鄰元素，前大於後則交換
2. 每輪遍歷將當前最大元素「冒泡」至末尾
3. 後續輪次遞減遍歷範圍，直到無交換發生

基礎實現

public void sort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

優化版：早停機制

引入 swapped 標誌，若某輪無交換說明已有序，提前終止。

public void sort(int[] array) {
    boolean swapped;
    int n = array.length;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (array[i - 1] > array[i]) {
                swap(array, i - 1, i);
                swapped = true;
            }
        }
        n--;
    } while (swapped);
}

二、選擇排序：精準定位，減少交換

改進動機

冒泡排序每次比較後可能交換，涉及三次賦值。選擇排序每輪僅在確定最小元素位置後進行一次交換，減少數據移動。

實現邏輯

1. 從未排序區間選出最小元素索引
2. 將其與區間首位元素交換
3. 重複直到整個數組有序

public void sort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) minIndex = j;
        }
        swap(array, i, minIndex);
    }
}

缺點：無論數據初始狀態如何，均需完整遍歷尋找最小值，無法利用已有序特性。

三、插入排序：就地構建有序區

核心隱喻

如同打牌整理手牌：將下一張牌插入已排好序的手牌中適當位置。

版本演進

V1：交換式插入（含早停優化）

for (int i = 1; i < array.length; i++) {
    for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
        swap(array, j, j - 1);
    }
}

V2：移位式插入（消除重複賦值）

for (int i = 1; i < array.length; i++) {
    int e = array[i];
    int j;
    for (j = i; j > 0 && array[j - 1] > e; j--) {
        array[j] = array[j - 1]; // 後移而非交換
    }
    array[j] = e; // 最後一次性放入
}

關鍵優勢

在近乎有序的數據上表現極佳（接近 O(n)），因內層循環極早觸發 break。這使其成為小規模、近乎有序數據的首選，也是希爾排序的基石。

四、希爾排序：插入排序的「分治」加速版

核心思想

將數組按增量 h 分為若干子序列（間隔 h 的元素），對各子序列進行插入排序，逐步縮小 h 至 1。利用「插入排序在近乎有序時極快」的特性，大幅減少數據移動總量。

增量序列選擇

常用 1, 4, 13, 40, 121... (3x+1) 序列，逆序使用。

完整實現

public void sort(int[] arr) {
    int n = arr.length;
    int h = 1;
    while (h < n / 3) h = 3 * h + 1; // 計算最大增量

    while (h >= 1) {
        // h-有序化
        for (int i = h; i < n; i++) {
            int e = arr[i];
            int j;
            for (j = i; j >= h && e < arr[j - h]; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = e;
        }
        h /= 3; // 遞減增量
    }
}

總結對比

理解這四種算法的演進脈絡——從「暴力交換」到「減少交換」，再到「利用有序性」，最後到「分治預排序」——是掌握更高級排序算法（快排、歸併、堆排）的認知基石。