常見排序算法 C 語言實現：冒泡、插入、選擇、快速、歸併

常見排序算法 C 語言實現：冒泡、插入、選擇、快速、歸併

本文提供五大經典排序算法的標準 C 實現，包含時間複雜度註釋，代碼風格統一，適合作為模板庫收藏。

1. 冒泡排序 —— O(n²)

void BubbleSort(int R[], int n) {
    int i, j, temp, flag;
    for(i = n; i >= 2; i--) {
        flag = 0;
        for(j = 2; j <= i; j++) {
            if(R[j-1] > R[j]) {
                temp = R[j-1];
                R[j-1] = R[j];
                R[j] = temp;
                flag = 1;
            }
        }
        if(flag == 0) return; // 已有序提前結束
    }
}

優化：單趟無交換則有序，提前返回。

2. 直接插入排序 —— O(n²)

void InsertSort(int R[], int n) {
    int i, j, temp;
    for(i = 2; i <= n; i++) {
        temp = R[i];
        j = i - 1;
        while(j >= 1 && R[j] > temp) {
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = temp;
    }
}

數組下標從 1 開始（R[0] 作哨兵或忽略）。

3. 選擇排序 —— O(n²)

void SelectSort(int R[], int n) {
    int i, j, temp, k;
    for(i = 1; i <= n; i++) {
        k = i;
        for(j = i+1; j <= n; j++)
            if(R[j] < R[k]) k = j;
        temp = R[i];
        R[i] = R[k];
        R[k] = temp;
    }
}

每趟選最小值與當前位置交換，不穩定。

4. 快速排序 —— O(n log n) 平均

void QuickSort(int R[], int l, int r) {
    int i = l, j = r, temp;
    if(l < r) {
        temp = R[l]; // 基準值
        while(i != j) {
            while(j > i && R[j] > temp) --j;
            if(i < j) { R[i] = R[j]; i++; }
            while(i < j && R[i] < temp) ++i;
            if(i < j) { R[j] = R[i]; j--; }
        }
        R[i] = temp;
        QuickSort(R, l, i);
        QuickSort(R, i+1, r);
    }
}

單邊掃描法，基準選首元素，易退化為 O(n²)（已有序）。工程上建議隨機化基準或三數取中。

5. 歸併排序 —— O(n log n) 穩定

void Merge(int R[], int low, int m, int high) {
    int i = low, j = m+1, p = 0;
    int *R1 = malloc((high-low+1)*sizeof(int));
    if(!R1) return;
    while(i <= m && j <= high)
        R1[p++] = (R[i] <= R[j]) ? R[i++] : R[j++];
    while(i <= m) R1[p++] = R[i++];
    while(j <= high) R1[p++] = R[j++];
    for(p = 0, i = low; i <= high; i++, p++)
        R[i] = R1[p];
    free(R1);
}

void MergeSort(int R[], int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;
        MergeSort(R, low, mid);
        MergeSort(R, mid+1, high);
        Merge(R, low, mid, high);
    }
}

需輔助數組，空間 O(n)，穩定排序，適合鏈表、外部排序。

算法綜合對比

工程選擇建議

• 通用高性能：qsort（C 標準庫，快速排序變體）
• 需穩定：歸併排序或 std::stable_sort（C++）
• 小數組/近乎有序：插入排序
• 嵌入式/極限空間：堆排序 O(1) 空間