C/C++ 八大經典排序算法原理與實現完全指南

穩定性定義

相等元素排序後相對順序不變 → **穩定**；可能改變 → **不穩定**。

1. 直接插入排序 (稳定, O(n²))

將無序區首元素插入有序區適當位置。優化：從右向左比較並後移。

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

2. 希爾排序 (不穩定, O(n^1.3~2))

分組插入排序，增量 d = n/2, d/2, ..., 1。

void shell_sort(int a[], int n) {
    for (int d = n/2; d > 0; d /= 2)
        for (int i = d; i < n; ++i) {
            int tmp = a[i], j = i-d;
            while (j >= 0 && tmp < a[j]) a[j+d] = a[j], j -= d;
            a[j+d] = tmp;
        }
}

3. 冒泡排序 (稳定, O(n²))

相鄰比較，大元素「冒泡」到右端。

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n-1; ++i)
        for (int j = n-2; j >= i; --j)
            if (a[j] > a[j+1]) std::swap(a[j], a[j+1]);
}

4. 快速排序 (不穩定, 平均 O(n log n))

分治法：選基準，分區 (左 ≤ 基準 < 右)，遞歸處理子區。經典「挖坑填數」法。

void quick_sort(int a[], int low, int high) {
    if (low >= high) return;
    int i = low, j = high, pivot = a[low];
    while (i < j) {
        while (i < j && a[j] >= pivot) --j;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) ++i;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    quick_sort(a, low, i-1);
    quick_sort(a, i+1, high);
}

5. 直接選擇排序 (不穩定, O(n²))

每輪選最小元素換到有序區末尾。

void select_sort(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        int k = i;
        for (int j = i+1; j < n; ++j) if (a[j] < a[k]) k = j;
        std::swap(a[i], a[k]);
    }
}

6. 堆排序 (不穩定, O(n log n))

建大根堆，反覆交換堆頂與末尾元素並調整堆。

void heap_adjust(int a[], int i, int size) {
    int l = 2*i+1, r = 2*i+2, max = i;
    if (l <= size && a[l] > a[max]) max = l;
    if (r <= size && a[r] > a[max]) max = r;
    if (max != i) { std::swap(a[i], a[max]); heap_adjust(a, max, size); }
}
void heap_sort(int a[], int n) {
    for (int i = n/2 - 1; i >= 0; --i) heap_adjust(a, i, n-1); // 建堆
    for (int i = n-1; i > 0; --i) {
        std::swap(a[0], a[i]);
        heap_adjust(a, 0, i-1);
    }
}

7. 歸並排序 (稳定, O(n log n))

分治：遞歸分解至單元素，合併兩有序區間。

void merge(int a[], int l, int m, int r) {
    vector tmp(r-l+1);
    int i = l, j = m+1, k = 0;
    while (i <= m && j <= r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = l, k = 0; i <= r; ++i, ++k) a[i] = tmp[k];
}
void merge_sort(int a[], int l, int r) {
    if (l >= r) return;
    int m = (l+r)/2;
    merge_sort(a, l, m);
    merge_sort(a, m+1, r);
    merge(a, l, m, r);
}

8. 基數排序 (稳定, O(d·n))

按位分配收集 (LSD)，適用非負整數。需輔助桶數組。

void radix_sort(int a[], int n) {
    int maxVal = *max_element(a, a+n);
    vector tmp(n), cnt(10);
    for (int exp = 1; maxVal/exp > 0; exp *= 10) {
        fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i < n; ++i) cnt[(a[i]/exp)%10]++;
        for (int i = 1; i < 10; ++i) cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; --i) tmp[--cnt[(a[i]/exp)%10]] = a[i];
        copy(tmp.begin(), tmp.end(), a);
    }
}

複雜度與選擇速查表

工程建議

• C++ 實戰直接用 std::sort (Introsort: 快速+堆+插入混合)、std::stable_sort (歸並)。
• 手寫排序僅用於面試、教學、極端定製場景 (如嵌入式無 STL)。
• 注意 std::sort 要求隨機訪問迭代器，鏈表用 list::sort。