七大經典排序算法深度解析與 C++ 實現指南

前言

排序算法是計算機科學中最基礎、最核心的算法之一，幾乎所有現代程式語言的標準庫都內建了高效的排序功能。然而，深入理解各類排序算法的原理、特性與複雜度，不僅是面試必考題，更能幫助開發者在面對特定問題時，選擇或設計出最優的解決方案。本文將系統梳理七種經典排序算法，包含原理圖解、核心步驟、C++ 代碼實現與複雜度分析，助你建立扎實的算法底子。

1. 冒泡排序

核心思想

冒泡排序是最直觀的排序方法。它重複遍歷待排序序列，比較相鄰兩個元素，若順序錯誤則交換。每一輪遍歷都能將當前未排序部分的最大值「冒泡」至末尾，就像氣泡上浮一樣。

算法步驟

1. 從序列左端開始，比較相鄰元素 x 和 y，若 x > y 則交換。
2. 繼續向右比較交換，直到到達序列末尾，此時最大元素已移至最右端。
3. 重複上述過程，每輪減少一個已排好序的尾部元素，共需 n-1 輪。

C++ 實現

void bubble_sort(std::vector<int> &nums) {
    for (int i = 0; i < nums.size() - 1; ++i) {
        for (int j = 0; j < nums.size() - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                std::swap(nums[j], nums[j + 1]);
            }
        }
    }
}

進階技巧：交換時可不使用臨時變數，利用算術運算或位運算（XOR）完成，但現代編譯器優化下 std::swap 效率通常更高且可讀性更強。

複雜度分析

• 時間複雜度：O(n²)。比較次數為等差數列求和 (n-1)+(n-2)+...+1 = n(n-1)/2。
• 空間複雜度：O(1)。原地排序，僅需常數額外空間。
• 穩定性：穩定排序（相等元素不交換位置）。

2. 插入排序

核心思想

插入排序模擬整理撲克牌的過程：將序列分為「已排序」與「未排序」兩部分，每次從未排序部分取出一個元素，在已排序部分中從右向左比較，找到合適位置插入。

算法步驟

1. 預設第一個元素有序，從第二個元素開始遍歷。
2. 取出當前元素 key，在已排序區間（左側）從右向左掃描。
3. 將大於 key 的元素向右移動一位，騰出空位。
4. 將 key 插入空位，完成本輪插入。

C++ 實現

void insertion_sort(std::vector<int> &nums) {
    for (int i = 1; i < nums.size(); ++i) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            --j;
        }
        nums[j + 1] = key;
    }
}

複雜度分析

• 時間複雜度：最好 O(n)（已有序），最壞/平均 O(n²)。
• 空間複雜度：O(1)。
• 穩定性：穩定。
• 適用場景：小規模數據、近乎有序的數據集表現極佳。

3. 選擇排序

核心思想

選擇排序每輪在未排序區間中找到最小（或最大）元素，將其與未排序區間的首位元素交換。雖然同為 O(n²)，但交換次數最少（最多 n-1 次），適合寫入操作昂貴的存儲介質。

C++ 實現

void selection_sort(std::vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
        int min_idx = i;
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] < nums[min_idx]) min_idx = j;
        }
        std::swap(nums[i], nums[min_idx]);
    }
}

複雜度分析

• 時間複雜度：恆為 O(n²)，與輸入數據無關。
• 空間複雜度：O(1)。
• 穩定性：不穩定（交換操作可能改變相等元素相對順序）。

4. 希爾排序

核心思想

希爾排序是插入排序的改進版，又稱「遞減增量排序」。它通過引入「間隔」將數組分為若干子序列分別進行插入排序，隨著間隔逐漸縮小至 1，數組基本有序，最終一次插入排序極快。常用間隔序列為 n/2, n/4, ..., 1（Shell 原始序列），更優序列如 Hibbard、Sedgewick 可進一步降低複雜度。

算法演示

以數組 [10, 80, 70, 100, 90, 30, 20] 為例，初始間隔 gap=3：

• 子序列 1: [10, 90] → 排序後 [10, 90]
• 子序列 2: [80, 30] → 排序後 [30, 80]
• 子序列 3: [70, 20] → 排序後 [20, 70]
• 子序列 4: [100]
• 合併後：[10, 30, 20, 90, 80, 70, 100]，再執行 gap=1 直接插入排序即可完成。

C++ 實現

void shell_sort(std::vector<int> &nums) {
    for (int gap = nums.size() / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < nums.size(); ++i) {
            int temp = nums[i];
            int j = i;
            while (j >= gap && nums[j - gap] > temp) {
                nums[j] = nums[j - gap];
                j -= gap;
            }
            nums[j] = temp;
        }
    }
}

複雜度分析

• 時間複雜度：依間隔序列而異。Shell 原始序列最壞 O(n²)，優化序列可達 O(n^(3/2)) 或 O(n log² n)。
• 空間複雜度：O(1)。
• 穩定性：不穩定。

5. 歸並排序

核心思想

典型的「分治法」代表。遞歸將數組二分至單元素，再合併兩個有序子數組。合併過程需輔助數組，保證穩定性與 O(n log n) 的最壞情況性能。

C++ 實現

void merge_array(std::vector<int> &nums, int left, int mid, int right, std::vector<int> &temp) {
    int i = left, j = mid, k = left;
    while (i < mid && j < right) {
        temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
    }
    while (i < mid) temp[k++] = nums[i++];
    while (j < right) temp[k++] = nums[j++];
    for (i = left; i < right; ++i) nums[i] = temp[i];
}

void merge_sort(std::vector<int> &nums, int left, int right, std::vector<int> &temp) {
    if (right - left > 1) {
        int mid = (left + right) / 2;
        merge_sort(nums, left, mid, temp);
        merge_sort(nums, mid, right, temp);
        merge_array(nums, left, mid, right, temp);
    }
}

複雜度分析

• 時間複雜度：O(n log n)（最好/最壞/平均一致）。
• 空間複雜度：O(n)（需輔助數組）。
• 穩定性：穩定（合併時 <= 保證相等元素先後順序）。

6. 快速排序

核心思想

同為分治法，但採用「基準值」分區：選一基準，將小於基準的元素移左側，大於的移右側，遞歸處理左右子區間。原地分區版本無需額外空間，是實踐中最快的通用排序算法之一。

C++ 實現

版本一：雙指針原地分區

void quick_sort(std::vector<int> &nums, int left, int right) {
    if (left < right) {
        int pivot = nums[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= pivot) --j;
            while (i < j && nums[i] <= pivot) ++i;
            std::swap(nums[i], nums[j]);
        }
        std::swap(nums[left], nums[i]);
        quick_sort(nums, left, i - 1);
        quick_sort(nums, i + 1, right);
    }
}

版本二：三路快排（針對大量重複元素優化，此處略）。

複雜度分析

• 時間複雜度：平均 O(n log n)，最壞 O(n²)（已有序且選首元素為基準），可通過隨機化基準或三數取中避免。
• 空間複雜度：O(log n)（遞歸棧深度），最壞 O(n)。
• 穩定性：不穩定。

7. 堆排序

核心思想

利用「最大堆」特性：堆頂恆為最大值。先將數組建堆，再反覆交換堆頂與末尾元素、縮小堆範圍並調整堆，即可得到有序序列。堆用數組隱式表示完全二叉樹，父子索引關係：parent = (i-1)/2, left = 2i+1, right = 2i+2。

算法流程

1. 建堆：從最後一個非葉節點（n/2 - 1）向前依次下沉調整。
2. 排序：交換堆頂與當前末尾，堆大小 -1，對新堆頂下沉調整，重複直到堆大小為 1。

C++ 實現

void max_heapify(std::vector<int> &nums, int root, int end) {
    int curr = root;
    int child = 2 * curr + 1;
    while (child <= end) {
        if (child + 1 <= end && nums[child] < nums[child + 1]) ++child;
        if (nums[curr] >= nums[child]) break;
        std::swap(nums[curr], nums[child]);
        curr = child;
        child = 2 * curr + 1;
    }
}

void heap_sort(std::vector<int> &nums) {
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; --i) max_heapify(nums, i, n - 1);
    for (int i = n - 1; i > 0; --i) {
        std::swap(nums[0], nums[i]);
        max_heapify(nums, 0, i - 1);
    }
}

複雜度分析

• 時間複雜度：O(n log n)（建堆 O(n)，n 次調整各 O(log n)）。
• 空間複雜度：O(1)。
• 穩定性：不穩定。
• 應用亮點：求 Top-K 問題（建大小為 K 的小頂堆）效率極高。

總結與選型建議

算法	平均時間	最壞時間	空間	穩定	推薦場景
冒泡/選擇/插入	O(n²)	O(n²)	O(1)	視具體實現	教學、極小數據、近乎有序
希爾排序	O(n^1.3~1.5)	O(n²)	O(1)	否	中等規模、嵌入式受限環境
歸並排序	O(n log n)	O(n log n)	O(n)	是	外部排序、鏈表、需穩定性
快速排序	O(n log n)	O(n²)	O(log n)	否	通用內存排序首選（隨機化版）
堆排序	O(n log n)	O(n log n)	O(1)	否	實時系統、Top-K、空間受限

實際工程中，C++ std::sort 採用 Introsort（快排+堆排+插入排混合），std::stable_sort 採用歸並排序，性能與穩健性兼備。理解底層原理，才能在特殊場景（如海量數據外排、特定硬件約束）下做出正確抉擇。