七大經典排序算法 C++ 實現與核心邏輯解析

排序算法是演算法面試與工程實踐的基石。本文提供七種常見排序算法的 C++ 實現，並針對每種算法解析核心邏輯、時間/空間複雜度及優化要點。所有算法以 vector<int> 為輸入，原地排序（歸並排序除外需輔助空間）。

算法複雜度速查表

1. 冒泡排序

重複遍歷數組，比較相鄰元素並交換，大元素像氣泡般「浮」到末尾。優化版加入標誌位，若某輪無交換則提前結束。

void bubbleSort(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        bool swapped = false;
        for (int j = n - 2; j >= i; --j) {
            if (a[j+1] < a[j]) {
                swap(a[j+1], a[j]);
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序
    }
}

2. 選擇排序

每輪從未排序部分選出最小元素，與未排序區首位交換。交換次數固定 O(n)，但比較次數仍 O(n²)。

void selectSort(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        int minIdx = i;
        for (int j = i+1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        if (i != minIdx) swap(a[i], a[minIdx]);
    }
}

3. 插入排序

模擬整理撲克牌：將當前元素插入已排序區的正確位置。對近乎有序數組極其高效（接近 O(n)）。

void insertSort(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = key;
    }
}

4. 希爾排序

插入排序的改進：按增量分組進行插入排序，逐步縮小增量至 1。常用增量序列：n/2, n/4, ..., 1 或 inc = inc/3 + 1（本文採用）。

void shellSort(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    for (int gap = n/2; gap > 0; gap = gap/2) { // 或 gap = gap/3 + 1
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i;
            while (j >= gap && a[j-gap] > key) {
                a[j] = a[j-gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

5. 堆排序

利用大頂堆特性：先建堆（從最後一個非葉節點向前 heapAdjust），再反覆交換堆頂與堆尾並縮小堆範圍重建。原地、不穩定、保證 O(n log n)。

void heapAdjust(vector<int>& a, int root, int size) {
    int largest = root;
    int left = 2*root + 1, right = 2*root + 2;
    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest != root) {
        swap(a[root], a[largest]);
        heapAdjust(a, largest, size);
    }
}

void heapSort(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    // 建堆
    for (int i = n/2 - 1; i >= 0; --i) heapAdjust(a, i, n);
    // 排序
    for (int i = n-1; i > 0; --i) {
        swap(a[0], a[i]);
        heapAdjust(a, 0, i);
    }
}

6. 歸並排序

分治法典範：遞歸拆分至單元素，再合併兩個有序子數組。穩定、O(n log n)，需 O(n) 輔助空間。本實現採用雙緩衝區避免重複分配。

void mergeSort(vector<int>& a) {
    if (a.empty()) return;
    vector<int> tmp(a.size());
    mSort(a, tmp, 0, a.size()-1);
}

void mSort(vector<int>& src, vector<int>& dst, int l, int r) {
    if (l == r) { dst[l] = src[l]; return; }
    int mid = (l + r) / 2;
    mSort(src, dst, l, mid);
    mSort(src, dst, mid+1, r);
    // 合併 dst[l..mid] 和 dst[mid+1..r] 到 src[l..r]
    merge(dst, src, l, mid, r);
}

void merge(vector<int>& src, vector<int>& dst, int l, int mid, int r) {
    int i = l, j = mid+1, k = l;
    while (i <= mid && j <= r)
        dst[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
    while (i <= mid) dst[k++] = src[i++];
    while (j <= r) dst[k++] = src[j++];
}

7. 快速排序

分治法：選基準，將數組分為「小於基準」與「大於基準」兩部分，遞歸排序。關鍵在於分區策略。本文採用雙指針法（Hoare 分區）。隨機化選基準可避免最壞情況。

void quickSort(vector<int>& a) {
    if (a.empty()) return;
    qSort(a, 0, a.size()-1);
}

void qSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int i = l, j = r;
    int pivot = a[l + rand() % (r - l + 1)]; // 隨機基準
    while (i <= j) {
        while (a[i] < pivot) ++i;
        while (a[j] > pivot) --j;
        if (i <= j) swap(a[i++], a[j--]);
    }
    if (l < j) qSort(a, l, j);
    if (i < r) qSort(a, i, r);
}

工程實踐建議

• 小數組 (n < 50)：插入排序常因常數因子小而最快。
• 通用高性能：std::sort (Introsort：快排+堆排+插排混合) 是首選。
• 需要穩定：std::stable_sort (歸並排序) 或自行實現歸並。
• 近乎有序：插入排序 / Timsort (Python/Java 採用)。
• 嵌入式/內存受限：堆排序 (O(1) 空間、保證 O(n log n))。