經典排序算法 C 語言實現：冒泡、選擇、插入排序完整教程

三大基礎排序算法原理、代碼實現與性能對比

冒泡、選擇、插入排序是演算法入門必修課，雖時間複雜度均為 O(n²)，但理解其機制是掌握快排、歸並、堆排等進階算法的基石。本文提供標準 C 實現、步驟圖解、優化技巧與適用場景分析。

一、冒泡排序：大元素「冒泡」到末尾

核心思想

相鄰元素兩兩比較，逆序則交換。每輪將當前最大元素移至未排序區末尾。

過程演示 (8 個數，降序)

初始: 4 9 10 3 2 14 11 5
第1輪: 9 10 4 3 14 11 5 2  (7次比較, 14冒泡到最前)
第2輪: 10 9 4 14 11 5 3 2  (6次比較, 11冒泡到第2)
...
最終: 14 11 10 9 5 4 3 2

標準實現

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {          // n-1 輪
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {  // 每輪比較次數遞減
            if (a[j] < a[j + 1]) {             // 降序: < ; 升序: >
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 優化: 本輪無交換已有序
    }
}

關鍵點

• 雙重循環：外層控制輪數，內層控制比較次數 (n-1-i)。
• 優化：增加 swapped 標誌，最好情況 O(n) (已有序)。
• 穩定性：穩定 (相等元素不交換，相對順序不變)。

二、選擇排序：每輪選極值放到已排區末尾

核心思想

在未排序區找到最大值，與未排序區首位交換。每輪確定一個元素最終位置。

過程演示 (同樣數據，降序)

初始: 4 9 10 3 2 14 11 5
第1輪: 14 9 10 3 2 4 11 5  (7次比較, 14與首位4交換)
第2輪: 14 11 10 3 2 4 9 5   (6次比較, 11與第2位9交換)
...
最終: 14 11 10 9 5 4 3 2

標準實現

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int max_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] > a[max_idx]) max_idx = j;  // 降序找最大
        }
        if (max_idx != i) {
            int tmp = a[i];
            a[i] = a[max_idx];
            a[max_idx] = tmp;
        }
    }
}

關鍵點

• 交換次數最少：最多 n-1 次交換，適合寫入開銷大的存儲介質 (如 EEPROM)。
• 不穩定：交換可能改變相等元素相對順序 (如 5a, 5b, 3 → 選 5a 與 3 交換 → 3, 5b, 5a)。
• 比較次數固定：n(n-1)/2，無最好情況優化。

三、插入排序：構建有序區，新元素插入合適位置

核心思想

維護前 i 個元素有序，將第 i+1 個元素向前比較移動，插入正確位置。類似整理撲克牌。

過程演示 (插入單個元素到有序數組)

有序區: 3 5 6 8 15 17 20 21 45 50
插入 25:
比較 50>25 右移, 45>25 右移, 21<25 停止
結果: 3 5 6 8 15 17 20 21 25 45 50

標準實現

void insertion_sort(int a[], int n) {
    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;
    }
}

關鍵點

• 最好情況 O(n)：已有序時內層不執行，僅比較不移動。
• 穩定：相等元素不移動 (a[j] > key 不含等號)。
• 適合小規模數據 (n < 50) 或近乎有序 數據；實際工程中常作為快排/歸並的小區間基礎排序。
• 二分查找優化比較次數 (O(n log n) 比較)，但移動仍 O(n²)，稱為二分插入排序。

四、三大算法綜合對比

五、工程實戰建議

1. n < 50：直接用插入排序 (常數因子小、適應性好)。
2. 通用排序：qsort (C 標準庫快排) / C++ std::sort (內省排序 O(n log n) 保證)。
3. 穩定排序需求：歸並排序 / std::stable_sort。
4. 嵌入式/內核：插入排序或選擇排序 (代碼極簡、棧開銷小、無遞歸)。
5. 避免：在生產代碼中直接使用 O(n²) 排序處理大數據集。

掌握三大基礎排序的微觀機制、穩定性差異、優化方向，是演算法工程化的起點。實際開發中，優先使用標準庫排序，僅在極受限環境或教學演示時手寫實現。

1. 上一篇文章： C 語言編譯與執行全流程深度解析：從原始碼到可執行檔案
2. 下一篇文章： Qtun 專案實戰：嵌入 Lua 腳本引擎實現靈活配置與插件擴展

關於C語言

Head First C# 中文版第二章 (Page 70-73)：常見概念問答與章節重點總結

精選問答 Q: 所有程式碼都要在類別裡嗎？ A: 是。指令

C# 語法學習：裝箱 Boxing 與拆箱 Unbox 基礎觀念與隱性發生場景 (1)

基礎範例：隱性裝箱拆箱計數 using Syst

C# 發現之旅第十四講：動態編譯 VB.NET 腳本引擎（下）

編輯腳本功能 工具列「編輯腳本」按鈕事件： private

從零構建 C 語言輕量級配置檔解析庫

專案背景與動機 在嵌入式或系統級開發中，JSON、XML 等