C語言排序與查找算法精講：冒泡、選擇、插入、二分查找的原理、代碼與優化

排序算法對比總覽

核心 O(n²) 算法深度實現

1. 冒泡排序：相鄰比較，大元素「冒泡」到末尾

void bubble_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        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; // 優化：本輪無交換已有序
    }
}

優化點：`swapped` 標誌提前終止；雙向冒泡（雞尾酒排序）減少來回。

2. 選擇排序：每輪選最小，與首位交換

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 tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp;
        }
    }
}

特性：交換次數固定 n-1 次（最少），但比較次數固定 n(n-1)/2，不適應數據狀態。

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

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)（已有序）。
• 穩定、原地、適應性強。
• 小數組（n < 50）實際比快排快（常數小），常作快排/歸併的基線排序。
• 支持在線排序（數據流到達即插入）。

4. 希爾排序：插入排序的間隔改進版（進階）

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

時間複雜度視間隔序列而定（如 Hibbard O(n^{3/2})、Sedgewick O(n^{4/3})），工程常用。

查找算法

1. 順序查找：O(n)，無序數組唯一選擇

int linear_search(const int *a, int n, int key) {
    for (int i = 0; i < n; ++i)
        if (a[i] == key) return i;
    return -1;
}

2. 二分查找：O(log n)，前提有序數組

// 迭代版（推薦，無棧開銷）
int binary_search(const int *a, int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // 防溢出
        if (a[mid] == key) return mid;
        else if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 遞歸版
int binary_search_rec(const int *a, int lo, int hi, int key) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == key) return mid;
    return a[mid] < key ? binary_search_rec(a, mid + 1, hi, key)
                        : binary_search_rec(a, lo, mid - 1, key);
}

3. 二分查找變體：下界/上界（C++ STL `lower_bound/upper_bound`）

// 返回第一個 >= key 的位置（若全 < key 返回 n）
int lower_bound(const int *a, int n, int key) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 返回第一個 > key 的位置
int upper_bound(const int *a, int n, int key) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 統計 key 出現次數
int count_occurrences(const int *a, int n, int key) {
    return upper_bound(a, n, key) - lower_bound(a, n, key);
}

標準庫 `qsort` 與 `bsearch` 實戰

#include 

int cmp_int(const void *a, const void *b) {
    int ia = *(const int*)a;
    int ib = *(const int*)b;
    return (ia > ib) - (ia < ib); // 避免溢出，返回 -1/0/1
}

int main() {
    int a[] = {9, 3, 5, 1, 7};
    int n = sizeof(a)/sizeof(a[0]);
    
    qsort(a, n, sizeof(int), cmp_int); // 快速排序（實現相關）
    
    int key = 5;
    int *found = bsearch(&key, a, n, sizeof(int), cmp_int);
    if (found) printf("Found at index %ld\n", found - a);
    else puts("Not found");
    
    return 0;
}

工程落地建議

1. 小數據（n < 50）：直接插入排序。
2. 通用排序：`qsort` + 比較函數，或 C++ `std::sort`（模板、內聯、更快）。
3. 近乎有序：插入排序或 Timsort（Python/Java 默認）。
4. 穩定性要求：歸併排序、`stable_sort`。
5. 查找頻繁：排序後二分，或改用哈希表/平衡樹（`uthash`、C++ `unordered_map`/`map`）。
6. 嵌入式/實時：堆排序（確定性 O(n log n)）、計數排序/基數排序（整數、範圍小）。

總結

排序與查找是算法基石。插入排序以適應性強、常數小成為小規模/近乎有序首選；二分查找及其變體是有序數組查找標準解；工程中優先標準庫 `qsort/bsearch` 或 C++ STL，僅在極致性能、特殊約束（嵌入式、實時、穩定、外部排序）下手寫。理解各算法時空權衡、穩定性、適應性，方能因地制宜。