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

题目

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

思路

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

解题分析

有序数组插入：找第一个 >x 的位置，后面元素整体后移。从尾部往前挪避免覆盖。也可先找下标再写 x。

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 3;
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) a[i] = 1;
        int x = 3;
        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++) System.out.print(a[i] + (i < n ? " " : "\n"));
    }
}

运行示例

输出：

1 2 3 5