C語言經典排序算法全解析：從選擇排序到快速排序

編輯：關於C語言

排序算法基礎概念

在深入具體算法之前，我們先釐清幾個核心概念，這對於理解後續各種排序的特性至關重要。

穩定性：相等元素的相對順序

所謂穩定排序，是指所有相等的數值經過排序後，仍能保持它們在排序前的相對次序。反之則為非穩定排序。例如：一組數排序前為 a1, a2, a3, a4, a5，其中 a2 = a4。若排序後變為 a1, a2, a4, a3, a5，則稱該排序穩定，因為 a2 排序前在 a4 前面，排序後仍在 a4 前面；若變為 a1, a4, a2, a3, a5 則不穩定。

內排序與外排序

內排序：排序過程中所有數據均在內存中，並在內存中調整存儲順序。
外排序：排序過程中僅部分數據被調入內存，借助內存調整外存中的存放順序。

時間複雜度與空間複雜度

時間複雜度：指執行算法所需的計算工作量。
空間複雜度：指執行算法所需的內存空間。

常見排序算法詳解與 C 語言實現

1. 選擇排序

算法思想：在待排序數組中，選出最小的數與第一個位置交換；然後在剩餘數中找最小的與第二個位置交換，以此類推，直到倒數第二個數與最後一個數比較為止。

特性：不穩定排序，時間複雜度 O(n²)。

void select_sort(int *x, int n) {
    int i, j, min, t;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (*(x + j) < *(x + min)) {
                min = j;
            }
        }
        if (min != i) {
            t = *(x + i);
            *(x + i) = *(x + min);
            *(x + min) = t;
        }
    }
}

2. 直接插入排序

算法思想：假設前 n-1 個數已排好序，將第 n 個數插入前面的有序序列中，使這 n 個數也有序。重複此過程直到全部排序完成。

特性：穩定排序，時間複雜度 O(n²)。

void insert_sort(int *x, int n) {
    int i, j, t;
    for (i = 1; i < n; i++) {
        t = *(x + i);
        for (j = i - 1; j >= 0 && t < *(x + j); j--) {
            *(x + j + 1) = *(x + j);
        }
        *(x + j + 1) = t;
    }
}

3. 冒泡排序（改進版）

算法思想：對未排序範圍內的所有數，自上而下比較相鄰兩數，大的下沉、小的上冒。改進版記錄每遍掃描後最後下沉位置 k，減少外層循環次數。

特性：穩定排序，時間複雜度 O(n²)。

void bubble_sort(int *x, int n) {
    int j, k, h, t;
    for (h = n - 1; h > 0; h = k) {
        for (j = 0, k = 0; j < h; j++) {
            if (*(x + j) > *(x + j + 1)) {
                t = *(x + j);
                *(x + j) = *(x + j + 1);
                *(x + j + 1) = t;
                k = j;
            }
        }
    }
}

4. 希爾排序

算法思想：直接插入排序每次僅增加一個節點，希爾排序通過相隔一定增量 d 分組，使數據移動時能跨越多個元素。先按增量 d 分組排序，再逐漸減小增量，直到增量為 1 時完成排序。本實現採用初次取序列一半為增量，之後每次減半的策略。

特性：不穩定排序。

void shell_sort(int *x, int n) {
    int h, j, k, t;
    for (h = n / 2; h > 0; h = h / 2) {
        for (j = h; j < n; j++) {
            t = *(x + j);
            for (k = j - h; k >= 0 && t < *(x + k); k -= h) {
                *(x + k + h) = *(x + k);
            }
            *(x + k + h) = t;
        }
    }
}

5. 快速排序

算法思想：採用分治法，選取基準值，將數組分為兩部分，左側小於基準值，右側大於基準值，再遞歸處理左右兩部分。

特性：不穩定排序，平均時間複雜度 O(n log n)。

void quick_sort(int *x, int left, int right) {
    if (left >= right) return;
    int i = left, j = right;
    int pivot = x[(left + right) / 2];
    int temp;
    do {
        while (x[i] < pivot) i++;
        while (x[j] > pivot) j--;
        if (i <= j) {
            temp = x[i];
            x[i++] = x[j];
            x[j--] = temp;
        }
    } while (i <= j);
    if (left < j) quick_sort(x, left, j);
    if (i < right) quick_sort(x, i, right);
}

總結對比

算法	穩定性	時間複雜度	適用場景
選擇排序	不穩定	O(n²)	小規模數據、空間受限
直接插入排序	穩定	O(n²)	小規模、近乎有序數據
冒泡排序	穩定	O(n²)	教學演示、極小數據集
希爾排序	不穩定	O(n^1.3~n²)	中等規模數據
快速排序	不穩定	O(n log n)	大規模數據、通用高效排序