三大經典排序算法 C 語言實現：選擇、插入、冒泡排序

排序算法入門三部曲：選擇、插入、冒泡完整代碼與原理圖解

排序是計算機科學基礎課核心內容。本文提供三種 O(n²) 經典排序的 C 語言標準實現，包含讀取輸入、菜單選擇、排序邏輯、結果輸出的完整可運行程序，並逐行解析核心邏輯。

完整可運行程序

#include 
#include 

void read_data(int a[], int n);
void write_data(int a[], int n);
void selection_sort(int a[], int n);
void insertion_sort(int a[], int n);
void bubble_sort(int a[], int n);

int main() {
    int n = 0, choice = 0, a[200];
    printf("請輸入元素個數：");
    scanf("%d", &n);
    printf("選擇排序方法（1.選擇 2.插入 3.冒泡）：");
    scanf("%d", &choice);
    read_data(a, n);
    switch (choice) {
        case 1: selection_sort(a, n); break;
        case 2: insertion_sort(a, n); break;
        case 3: bubble_sort(a, n); break;
        default: printf("無效選擇\n"); return 1;
    }
    write_data(a, n);
    return 0;
}

void read_data(int a[], int n) {
    printf("請輸入 %d 個整數：", n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
}
void write_data(int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
}

核心排序函數實現與邏輯解析

1. 選擇排序 Selection Sort

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min_idx]) min_idx = j;
        if (min_idx != i) {
            int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
        }
    }
}

原理： 每輪從未排序區間選出最小元素，換到已排序區間末尾。
特點： 交換次數最少（≤ n-1），但比較次數固定 O(n²)，不穩定。

2. 插入排序 Insertion Sort

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

原理： 將第 i 個元素插入前面已排好序的子數組適當位置，類似整理撲克牌。
特點： 近乎有序時 O(n) 最優，穩定，適合小規模/基本有序數據。

3. 冒泡排序 Bubble Sort

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        if (!swapped) break; // 優化：本輪無交換則已有序
    }
}

原理： 相鄰元素兩兩比較，大的「冒泡」到右端。每輪確定一個最大值位置。
特點： 可優化提前終止，穩定，代碼最簡潔，教學價值高但實用性低。

複雜度與特性對比

工程實踐建議

• 實際項目中 **優先使用庫函數** `qsort`（快速排序 O(n log n)）或 C++ `std::sort`（內省排序）。
• 嵌入式極小數組（<50）且對代碼體積敏感時，插入排序是不錯選擇。
• 理解這三者是學習歸併、快速、堆排序的基石，重點掌握**循環不變量**思維。