江苏省建设人才网站,营山网站建设,聊城网站开发培训,wordpress上传ppt题目#xff1a;有一个已经排好序的数组。现输入一个数#xff0c;要求按原来的规律将它插入数组中。
程序分析
要将一个数插入已经排好序的数组中#xff0c;我们可以采用以下步骤#xff1a;
遍历数组#xff0c;找到第一个大于待插入数的位置。将待插入数插入到该位…题目有一个已经排好序的数组。现输入一个数要求按原来的规律将它插入数组中。
程序分析
要将一个数插入已经排好序的数组中我们可以采用以下步骤
遍历数组找到第一个大于待插入数的位置。将待插入数插入到该位置同时将该位置后面的元素依次后移一位。
下面我们将使用三种不同的方法来实现这个任务并分析它们的优缺点。
方法一遍历插入
解题思路
我们可以遍历已排序数组找到第一个大于待插入数的位置然后将待插入数插入该位置。
实现代码
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(ArrayListInteger 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) {ArrayListInteger 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。
总的来说方法二二分查找插入通常是更好的选择因为它兼顾了性能和实现复杂度。
