C 语言第35题：在有序数组中插入一个新数并保持有序

题目

已知一个包含 n 个整数的非降序有序数组，再输入一个整数 x，将 x 插入到数组中合适的位置，使插入后的新数组依然保持有序。

输入格式：第一行输入原数组大小 n；第二行输入 n 个升序整数；第三行输入待插入的整数 x。

输出格式：在一行中输出插入新元素后的完整数组，元素以空格分隔，末尾换行。

数据范围与约定：0 ≤ n ≤ 500。

思路与算法

1. 从后向前扫描与元素搬移
数组容量需预留 +1 位置。从数组末尾 pos = n 开始向前查找，只要 pos > 0 && a[pos-1] > x，就将前一个元素后移 a[pos] = a[pos-1]; pos--;。

2. 落位写入
循环终止时的 pos 即为正确插入点，执行 a[pos] = x。从后向前边比边移避免了覆盖数据。

完整程序

#include <stdio.h>

int main(void)
{
    int n, x, a[501];
    if (scanf("%d", &n) != 1 || n < 0 || n > 500) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &x);

    // 从后往前扫描，将所有比 x 大的元素依次往后挪动一位，腾出插入位置
    int pos = n;
    while (pos > 0 && a[pos - 1] > x) {
        a[pos] = a[pos - 1];
        pos--;
    }
    // 将 x 放入腾出的正确有序位置
    a[pos] = x;

    for (int i = 0; i <= n; i++) {
        printf("%d%c", a[i], i < n ? ' ' : '\n');
    }
    return 0;
}

运行示例

输入：

3
1 3 5
2

输出：

1 2 3 5