經典排序算法系列（一）：冒泡排序與快速排序深度解析

編輯：關於C語言

前言：排序是算法入門的「Hello World」

排序算法按數據是否在內存中完成分為內排序（本文重點）與外排序。內排序按思想分：插入類（直接插入、希爾）、交換類（冒泡、快速）、選擇類（簡單選擇、堆排序）、歸併類、基數類。本文深度解析交換類兩大代表——冒泡與快速，從原理、代碼、優化、複雜度、穩定性全維度對比。

一、冒泡排序

1. 核心思想

相鄰元素兩兩比較，大的「冒泡」到右側。每趟確定一個最大值位置，共需 n-1 趟。

2. 標準實現（遞增序）


void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false; // 優化標誌
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 本趟無交換，已有序，提前結束
    }
}

3. 關鍵屬性

屬性	值
時間複雜度	最好 O(n)（有序）、平均/最壞 O(n²)
空間複雜度	O(1)
穩定性	穩定（相等元素不交換）
適用場景	小規模、近乎有序、教學演示

4. 原文代碼問題

原文雙層循環邏輯混亂（h、p、j 混用），且缺少交換後的邊界更新，實際無法正確排序。上方代碼為修正版。

二、快速排序——冒泡的「分治進化版」

1. 核心思想：分治 + 基準值 Partition

選取 基準值（通常取首/尾/中/隨機元素）。
Partition：將數組劃分為「≤ 基準」與「≥ 基準」兩區，基準落在最終位置。
遞歸處理左右子區。

2. Hoare Partition 單趟劃分邏輯（原文採用）

初始: [key, ..., ..., ...]  low=0, high=n-1
1. high 向左找 < key
2. low  向右找 > key
3. 交換 low/high
4. 重複直到 low >= high
5. 基準歸位

3. 完整 C++ 實現（含隨機基準優化）


#include <algorithm>
#include <random>

int partition(int arr[], int low, int high) {
    // 隨機選基準，避免有序數組退化 O(n²)
    std::swap(arr[low], arr[low + rand() % (high - low + 1)]);
    int key = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= key) --high;
        arr[low] = arr[high];
        while (low < high && arr[low] <= key) ++low;
        arr[high] = arr[low];
    }
    arr[low] = key;
    return low;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = partition(arr, low, high);
        quickSort(arr, low, mid - 1);
        quickSort(arr, mid + 1, high);
    }
}

4. 關鍵屬性

屬性	值
時間複雜度	平均 O(n log n)、最壞 O(n²)（可隨機化避免）
空間複雜度	O(log n) 遞歸棧（尾遞歸優化可至 O(1)）
穩定性	不穩定（Partition 交換可能改變相等元素相對序）
實際表現	內排序最快，標準庫 `std::sort` 多為 Introsort（快排+堆排混合）

5. 原文代碼缺陷

固定取首元素為基準，有序/逆序數組退化為 O(n²)。
Partition 邏輯中 R.r[0] = R.r[s] 用哨兵位但未恢復，易錯。
遞歸邊界 QuickSort(R, s, low-1) 若 low==s 會傳入無效區間，需 if (low < high) 守護。

三、冒泡 vs 快速：全方位對比

維度	冒泡排序	快速排序
核心操作	相鄰交換	基準劃分 + 大跨度交換
數據移動次數	多（每次移動 1 位）	少（直接跳到大致位置）
緩存友好度	高（順序訪問）	中（跳躍訪問）
穩定性	穩定	不穩定
工程應用	極小數組 (n<50)、近乎有序	通用高效排序首選