JAVA练习百题之数组插入元素

题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。

程序分析

要将一个数插入已经排好序的数组中，我们可以采用以下步骤：

1. 遍历数组，找到第一个大于待插入数的位置。
2. 将待插入数插入到该位置，同时将该位置后面的元素依次后移一位。

下面我们将使用三种不同的方法来实现这个任务，并分析它们的优缺点。

方法一：遍历插入

解题思路

我们可以遍历已排序数组，找到第一个大于待插入数的位置，然后将待插入数插入该位置。

实现代码

public class Main {public static void insertSorted(int[] arr, int num) {int i;for (i = 0; i < arr.length; i++) {if (arr[i] > num) {break;}}// 将待插入数插入到位置 i，同时后面的元素后移for (int j = arr.length - 1; j > i; j--) {arr[j] = arr[j - 1];}arr[i] = num;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int num = 4;System.out.print("Original Array: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}insertSorted(arr, num);System.out.print("\nArray after insertion: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

优缺点

优点：

• 简单易懂，容易实现。
• 对于小规模数组或已经基本有序的数组，性能较好。

缺点：

• 对于大规模数组，性能较差，时间复杂度为O(n)。

方法二：二分查找 + 插入

解题思路

我们可以使用二分查找来快速找到待插入数的位置，然后再进行插入操作。

实现代码

public class Main {public static int binarySearch(int[] arr, int num) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == num) {return mid;} else if (arr[mid] < num) {left = mid + 1;} else {right = mid - 1;}}return left;}public static void insertSorted(int[] arr, int num) {int pos = binarySearch(arr, num);for (int i = arr.length - 1; i >= pos; i--) {arr[i] = arr[i - 1];}arr[pos] = num;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int num = 4;System.out.print("Original Array: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}insertSorted(arr, num);System.out.print("\nArray after insertion: ");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

优缺点

优点：

• 较方法一更高效，时间复杂度为O(log n)。
• 适用于大规模数组。

缺点：

• 实现稍微复杂一些。

方法三：使用ArrayList

解题思路

我们可以使用ArrayList来插入新元素，然后再将其转换为数组。

实现代码

import java.util.ArrayList;
import java.util.Arrays;public class Main {public static void insertSorted(ArrayList<Integer> list, int num) {int pos = 0;while (pos < list.size() && list.get(pos) < num) {pos++;}list.add(pos, num);}public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9));int num = 4;System.out.print("Original List: ");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}insertSorted(list, num);System.out.print("\nList after insertion: ");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}}
}

优缺点

优点：

• 使用ArrayList简化了插入操作。
• 适用于大规模数组。

缺点：

• 需要额外的内存空间来存储ArrayList。
• 对ArrayList的插入操作可能稍慢于直接操作数组。

总结

对于小规模数组，方法一或方法三都可以选择，具体取决于个人偏好。方法二在大规模数组中具有更好的性能，因为它的时间复杂度是O(log n)，但实现稍微复杂一些。

如果需要处理大规模数组，并且希望保持较高的性能，方法二（二分查找+插入）是一个更好的选择。如果空间使用不是主要考虑因素，也可以考虑方法三（使用ArrayList）。

总的来说，方法二（二分查找+插入）通常是更好的选择，因为它兼顾了性能和实现复杂度。