C 語言：冒泡排序後插入新元素保持有序輸出

題目：輸入 20 個整數 → 冒泡降序排序 → 再輸入 1 個數插入 → 輸出 21 個有序數。核心是插入位置查找 + 後移元素。

標準流程

1. 讀入 20 個數到數組 a[20]。
2. 冒泡排序（降序）：外層 i=0..18，內層 j=i+1..19，若 a[i] < a[j] 交換。
3. 讀入新數 x。
4. 從後向前掃描找到第一個 a[i] >= x 的位置 pos = i+1（插入點）。
5. pos..19 依次後移一位，a[pos] = x。
6. 輸出 a[0..20]。

參考代碼（修正原答案邏輯錯誤）

#include 

int main() {
    int a[21] = {0}, n = 20, x, i, j, temp;

    // 1. 讀入 20 個數
    printf("Input 20 integers:\n");
    for (i = 0; i < n; i++) scanf("%d", &a[i]);

    // 2. 冒泡降序
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[i] < a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; }

    printf("Sorted: ");
    for (i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");

    // 3. 讀入新數
    printf("Insert one integer: ");
    scanf("%d", &x);

    // 4. 找插入位置並後移
    int pos = n; // 默認插到末尾
    for (i = 0; i < n; i++) {
        if (a[i] <= x) { pos = i; break; } // 降序：遇到 <= x 就插在它前面
    }
    for (i = n; i > pos; i--) a[i] = a[i - 1];
    a[pos] = x;
    n++; // 長度變 21

    // 5. 輸出
    printf("After insert: ");
    for (i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

關鍵點提示

• 冒泡外層 n-1 趟，內層遞減，避免重複比較已排好區間。
• 插入查找利用已有序性，從前向後找第一個 <= x（降序）或 >= x（升序），O(n) 即可，無需二分（數據量小）。
• 後移循環 for(i=n; i>pos; i--) 必須從末尾向前，否則覆蓋數據。

掌握「排序 + 區間插入」模板，考試、OJ、面試手寫代碼全通關。