C語言數組插入算法：有序數組中按大小插入元素實現

算法邏輯

1. 確定排序方向（示例：降序）
2. 遍歷數組，找到首個 插入值 > 當前元素 的位置 i
3. 從數組末尾向前移動元素至位置 i
4. 將插入值賦給 a[i]
5. 若插入值最小，插入末尾

完整代碼實現

main() {
    int i, j, p, q, s, n;
    int a[11] = {127, 3, 6, 28, 54, 68, 87, 105, 162, 18};

    // 先降序排序
    for (i=0; i<10; i++) {
        p = i; q = a[i];
        for (j=i+1; j<10; j++)
            if (q < a[j]) { p = j; q = a[j]; }
        if (p != i) {
            s = a[i]; a[i] = a[p]; a[p] = s;
        }
        printf("%d ", a[i]);
    }

    // 插入新元素
    printf("\ninput number:\n");
    scanf("%d", &n);
    for (i=0; i<10; i++)
        if (n > a[i]) {
            for (s=9; s>=i; s--) a[s+1] = a[s]; // 後移
            break;
        }
    a[i] = n;

    // 輸出結果
    for (i=0; i<=10; i++) printf("%d ", a[i]);
    printf("\n");
}

關鍵細節

• 後移循環 從後向前（s=9; s>=i; s--），避免覆蓋
• break 跳出外層循環，i 保持插入位置
• 若全遍歷未 break，i=10，插入末尾 a[10]
• 數組大小預留 1 位（11）容納新元素

測試結果

輸入 47 → 插入 54 和 28 之間，輸出序列有序。

複雜度分析

• 時間：O(n) — 線性查找 + 線性移動
• 空間：O(1) — 原地操作
• 適用：小規模有序數組動態維護

優化方向

• 二分查找定位插入位 → O(log n) 查找，移動仍 O(n)
• 大規模數據用鏈表/平衡樹避免移動開銷
• C++ vector::insert / list 封裝此邏輯

有序數組插入是數據結構基礎操作，掌握其邊界條件與移動邏輯至關重要。