怎样在数组中插入一个数，插入后该数组仍有序

有很多种方法可以在数组中插入一个数，以下是一种比较简单的方法：

1. 首先找到要插入的数字在数组中应该插入的位置。可以使用二分查找算法来找到位置，这样可以保证数组仍然有序。

2. 把要插入的数字插入到数组中，可以使用数组元素后移的方法来实现。从数组末尾开始往前遍历，找到第一个大于要插入数字的位置，将该位置后的所有数字往后移动一位，然后将要插入的数字插入到空出来的位置。

例如，假设现有一个有序数组arr，要插入的数字为num：

int[] arr = {1, 3, 5, 7, 9};
int num = 4;

// 找到要插入数字的位置
int pos = Arrays.binarySearch(arr, num);
if (pos < 0) {
pos = -(pos + 1);
}

// 将数字插入数组
for (int i = arr.length - 1; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = num;

// 输出结果
System.out.println(Arrays.toString(arr));

输出结果为：[1, 3, 4, 5, 7, 9]

相关问题

用C语言写一个程序在一个数组中插入一个数后该数组仍有序

#include <stdio.h>

int main() {
int arr[100], n, i, j, num;

//输入当前数组长度
printf("输入数组长度：");
scanf("%d", &n);

//输入数组元素
printf("输入数组元素：");
for(i=0; i<n; i++) {
scanf("%d", &arr[i]);
}

//输入要插入的数
printf("输入要插入的数：");
scanf("%d", &num);

//寻找要插入的位置
for(i=0; i<n; i++) {
if(num<=arr[i]) {
//将数组后面的元素全部后移
for(j=n-1; j>=i; j--) {
arr[j+1] = arr[j];
}
arr[i] = num;
n++; //数组长度加1
break;
}
}

//输出新数组
printf("新数组为：");
for(i=0; i<n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

java 在一个有序的数组中插入一个数，使得插入后的数组有序。

可以使用二分查找的思路，先确定插入的位置，再移动后续元素。具体实现为：

1. 使用二分查找确定新数应该插入的位置，得到插入点 insertIndex。
2. 将新数插入到 insertIndex 位置。
3. 从插入点开始遍历数组，将后续元素全部向后移动一个位置，直到数组末尾。

以下是实现示例代码：

public static void insertSorted(int[] arr, int num) {
    int len = arr.length;
    int insertIndex = binarySearchInsertPoint(arr, num);

    // 将新数插入到插入点
    for (int i = len - 1; i > insertIndex; i--) {
        arr[i] = arr[i-1];
    }
    arr[insertIndex] = num;
}

// 使用二分查找确定插入点
private static int binarySearchInsertPoint(int[] arr, int num) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == num) {
            return mid;
        } else if (arr[mid] < num) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return l;
}