C 語言實現經典排序與查找算法：順序、折半、冒泡、直接插入

編輯：關於C語言

前言

本文提供一個整合的教學級程式，實現四種基礎算法：哨兵順序查找、折半查找、冒泡排序、直接插入排序，並透過選單驅動互動測試。代碼遵循 C89 風格，適合初學者理解算法邏輯與陣列操作。

核心算法實現

1. 哨兵順序查找 `search`

int search(int a[], int n, int key) {
    int i = n - 1;
    a[0] = key;                 // 哨兵置於索引 0
    while (a[i] != key) i--;    // 必定終止，無需邊界檢查
    return i;                   // 返回 0 表示未找到
}

優點：省去循環內的邊界判斷，提升效率。缺點：修改了陣列第 0 元素（需呼叫端配合預留）。

2. 折半查找 `halfsearch`

int halfsearch(int a[], int n, int key) {
    int low = 1, high = n, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == a[mid]) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return 0;   // 未找到
}

前提：陣列**必須已排序**（遞增）。時間複雜度 O(log n)。

3. 冒泡排序 `mpsort`

void mpsort(int a[]) {
    int i, j, tmp;
    for (i = 1; i < N; i++)
        for (j = i + 1; j < N; j++)
            if (a[i] > a[j]) {
                tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            }
}

雙層迴圈兩兩比較交換，大值逐漸「沉底」。時間複雜度 O(n²)，教學用途為主。

4. 直接插入排序 `insertsort`

void insertsort(int a[]) {
    int i, j;
    for (i = 2; i < N; i++) {
        a[0] = a[i];          // 暫存待插元素
        j = i - 1;
        while (a[0] < a[j]) { // 向右移動已排序部分
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = a[0];      // 插入正確位置
    }
}

維護前段有序區，將新元素插入適當位置。近似有序資料時效能最佳，同為 O(n²) 但常數較小。

輔助函數與主程式架構

creat()：讀入 N-1 個整數（索引 1~N-1）。
print()：輸出排序後陣列。
main()：無限循環選單，goto aga 實現回主選單（教學簡易寫法，工程建議改用 while(1)）。

選單功能對照表

選項	操作流程
1	建立陣列 → 輸入查找鍵 → 哨兵順序查找 → 顯示位置
2	建立陣列 → 直接插入排序 → 顯示結果 → 輸入鍵 → 折半查找
3	建立陣列 → 直接插入排序 → 顯示結果
4	建立陣列 → 冒泡排序 → 顯示結果
5	退出程式