当前位置：首页 > news >正文

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

news 2025/6/30 11:03:56

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

程序分析

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

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

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

方法一：遍历插入

解题思路

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

实现代码

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) + " ");}}
}