版本一】
import java.util.Scanner; class Test30 { public static void main(String[] args) { int[] arr = {2,16,22,38,46,66,88,99}; Scanner sc = new Scanner(System.in); System.out.println("请输入要插入的数:"); int num = sc.nextInt(); //定义一个比原数组长度大一的空数组 int[] arr2 = new int[arr.length+1]; //如果输入的比有序数组的最后一个元素还大,就直接放到新数组的最后一个 if(num>arr[arr.length-1]){ arr2[arr2.length-1]=num; for(int i=0;i<arr.length;i++){ arr2[i] = arr[i]; } }else{ int i; for(i=0;i<arr.length;i++){ if(arr[i]<num){ arr2[i] = arr[i]; }else{ arr2[i] = num; break;//例如1,2,3,5,6;插入4;1,2,3,4,插入之后要跳出,否则后面就全是4 } } for(int j=i+1;j<arr2.length;j++){ arr2[j]=arr[j-1];//把剩下的元素添加尽量,例如上面的5,6 } } traverse(arr2); } //定义遍历方法 public static void traverse(int[] arr){ for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" ");//不换行遍历,以空格隔开 } System.out.println();//换行 } }版本二】
import java.util.Scanner; class Test30 { public static void main(String[] args) { int[] arr = {1,3,9,34,38,40,89,100,111,222,333}; Scanner sc = new Scanner(System.in); System.out.println("请输入要插入的数:"); int num = sc.nextInt(); //定义一个比原数组长度大一的空数组 int[] arr2 = new int[arr.length+1]; //版本二,通过折半查找进行插入 int insert = half(arr,num); for(int i=insert;i<arr.length;i++){ arr2[i+1]=arr[i]; } for(int i=0;i<insert;i++){ arr2[i]=arr[i]; } arr2[insert] = num; //System.out.println(mid); traverse(arr2); } //定义遍历方法 public static void traverse(int[] arr){ for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" ");//不换行遍历,以空格隔开 } System.out.println();//换行 } //折半查找退出的条件是min>max;此时mid可能指向min也可能指向max, //插入的位置只能是max和min中间,也就是min当前的下标,或者返回max+1; public static int half(int[] arr,int num){ int min = 0; int max = arr.length-1; int mid = 0; while(min<=max){ mid = (min+max)/2; if(num<arr[mid]){ max = mid - 1; }else if(num>arr[mid]){ min = mid + 1; }else{ return mid; } } return min; } }运行结果：
