經典排序算法深度解析：快速排序、插入排序、堆排序與線性排序

經典排序算法深度解析：快速排序、插入排序、堆排序與線性排序

排序算法是面試高頻考點，本文通過 Java 實現對比快速排序兩種分區策略、插入排序、堆排序核心邏輯，並概述計數/基數/桶排序等線性排序思想。

快速排序：分治法核心——分區

快速排序平均時間複雜度 O(n log n)，關鍵在於 partition 實現。對比兩種經典寫法：

版本 A：算法導論單向掃描法

private int partitionA(int begin, int end) {
    int pivot = arr.get(end); // 基準值
    int i = begin - 1;
    for (int j = begin; j < end; j++) {
        if (arr.get(j) <= pivot) {
            i++;
            swap(i, j);
        }
    }
    swap(i + 1, end);
    return i + 1; // 基準最終位置
}

思路：單指針 i 維護「≤基準」區域邊界，遍歷將小元素交換到左側。

版本 B：數據結構教材雙向掃描法

private int partitionB(int begin, int end) {
    int pivot = arr.get(end);
    int left = begin, right = end - 1;
    while (left <= right) {
        while (left <= end - 1 && arr.get(left) <= pivot) left++;
        while (right >= begin && arr.get(right) > pivot) right--;
        if (left < right) swap(left, right);
    }
    swap(left, end);
    return left;
}

思路：左右指針向中間收縮，交換左右錯位元素，最終將基準放至 left。

結論： 兩種分區遍歷次數相同，時間複雜度一致。版本 A 代碼更簡潔，版本 B 交換次數可能略少。

遞歸入口

private void quickSort(int begin, int end) {
    if (begin < end) {
        int q = partitionB(begin, end); // 或 partitionA
        quickSort(begin, q - 1);
        quickSort(q + 1, end);
    }
}

插入排序：樸素但 O(n²)

核心思想：維護左側有序區，將下一個元素插入正確位置（如整理撲克牌）。

private void insertionSort() {
    for (int i = 1; i < arr.size(); i++) {
        int p = 0;
        while (p < i && arr.get(p) < arr.get(i)) p++;
        if (p < i) {
            int temp = arr.get(i);
            for (int k = i; k > p; k--) arr.set(k, arr.get(k - 1)); // 後移
            arr.set(p, temp);
        }
    }
}

最好情況（已有序）O(n)，最壞/平均 O(n²)，穩定排序。

堆排序：利用完全二叉樹特性 O(n log n)

核心步驟：

1. 構建大頂堆：從最後一個非葉節點 (n/2 - 1) 向前調用 heapify
2. 重複：交換堆頂與末尾元素，堆大小 -1，重新 heapify 堆頂

private void heapify(int n, int i) {
    int largest = i;
    int l = 2*i + 1, r = 2*i + 2;
    if (l < n && arr.get(l) > arr.get(largest)) largest = l;
    if (r < n && arr.get(r) > arr.get(largest)) largest = r;
    if (largest != i) {
        swap(i, largest);
        heapify(n, largest); // 遞歸調整子樹
    }
}

private void heapSort() {
    // 建堆
    for (int i = arr.size()/2 - 1; i >= 0; i--) heapify(arr.size(), i);
    // 排序
    for (int i = arr.size() - 1; i > 0; i--) {
        swap(0, i);
        heapify(i, 0);
    }
}

線性排序：以空間換時間 O(n)

桶排序效率最高但要求數據分佈均勻且範圍已知；離散數據或未知範圍不適用。