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

题目

在有序数组中插入一个新数并保持有序

思路

本题在已有序数组中插入一个新数 key，插入后仍有序。

先找到第一个 a[i] > key 的位置 pos（即插入点）；把 pos 及之后的元素整体后移一位（memmove 或从尾向前循环）；在 pos 放入 key。若 key 最大则插在末尾。

解题分析

有序数组插入：找第一个 >x 的位置，后面元素整体后移。从尾部往前挪避免覆盖。也可先找下标再写 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);
    int pos = n;
    while (pos > 0 && a[pos - 1] > x) {
        a[pos] = a[pos - 1];
        pos--;
    }
    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