PC端主页可联系我，欢迎问题咨询和技术交流！

零、前言

我的学习策略很简单，题海策略+ 费曼学习法。如果能把这100题都认认真真自己实现一遍，那意味着 JAVA语言 已经筑基成功了。后面的进阶学习，可以继续跟着我，一起走向架构师之路。

题目描述：有一个已经排好序的数组

一、题目

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

二、解题思路

（插入排序）首先判断此数是否大于最后一个数，然后再考虑插入中间的数的情况，插入后此元素之后

的数，依次后移一个位置。

三、代码详解

public class Basics22 {
    public static void main(String[] args) {
        int i,x;
        Scanner input =  new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<Integer>();
        int arr[] = { 2, 9, 12, 23, 31, 47, 52, 78, 89, 95 };
        System.out.print("请输入需要插入的数字：");
        x=input.nextInt();

        for (i = 0; i < arr.length; i++){
            //把静态数组全部赋值给动态数组
            list.add(arr[i]);
        }

        for (i = 0; i < arr.length; i++){
            //用需要插入的数字与数组中的每一位进行对比
            //此时i的值则说明了该数处于数组中的位置
            if(x<list.get(i)){
                //把数字插入到数组中的第i位。
                list.add(i,x);
                break;
            }
           
        }
        for (i = 0; i < list.size(); i++){
            System.out.print(list.get(i)+" ");
        }
    }
}

解法二：冒泡排序

解题思路

因为已知数组是排好序的，这和冒泡排序进行最后轮排序是一样的。

所以第一步，将已知数组和需要插入的数字放到一个新的数组里，且把需要插入的数字放到新的数组的 最后一位。

然后进行冒泡排序，将最后一个数字放到合适的位置。

代码详解

public class Basics22_2 {
    public static void main(String[] args) {
        Scanner input =  new Scanner(System.in);
        int arr[] = { 2, 9, 12, 23, 31, 47, 52, 78, 89, 95 };
        System.out.print("请输入需要插入的数字：");
       int x=input.nextInt();
        int[] newArray =  inBubbleSort(arr,x);
        for (int i = 0; i < newArray.length; i++) {
            System.out.print(newArray[i]+" ");
        }
    }

    public static int[] inBubbleSort(int[] arr, int number) {
        int[] arrchange = new int[arr.length + 1];

        //将源数组复制到新的数组里，新数组最后一个元素为需要插入的数字
        for (int i = 0; i < arr.length; i++) {
            arrchange[i] = arr[i];
        }
        arrchange[arr.length] = number;

        //类似进行冒泡排序的最后一轮
        for (int i = arr.length; i > 0;i--) {
            if (arrchange[i] < arrchange[i - 1]) {
                int temp = arrchange[i];
                arrchange[i] = arrchange[i - 1];
                arrchange[i - 1] = temp;
            }
        }
        return arrchange;
    }

}

解法三：二分法

解题思路

1、找出已经排好序的数组的中间值，判断插入值跟中间值的大小；

2、如果等于，就OK了;如果不等，二分查找区间长度等于1，查找也OK了。

3、如果存在大小关系，就重复步骤1和步骤进行查找。

代码详解

public class Basics22_3 {
    public static void main(String[] args) {
       
        Scanner input = new Scanner(System.in);
        int arr[] = {2, 9, 12, 23, 31, 47, 52, 78, 89, 95};
        int[] arrchange = new int[arr.length + 1];
        System.out.print("请输入需要插入的数字：");
        int x = input.nextInt();
        for (int i = 0; i < arr.length; i++) {
			arrchange[i] = arr[i];
		}
        int location = inDichotomySort(arr, x);


		for (int i = arrchange.length - 1; i > location; i--) {
			arrchange[i] = arrchange[i - 1];
		}

		arrchange[location] = x;

		System.out.print("changed:  ");
		for (int i = 0; i < arrchange.length; i++) {
			 System.out.print(arrchange[i]+" ");
        }
    }

    public static int inDichotomySort(int[] arrchange, int number) {
        int low = 0;
        int high = arrchange.length - 1;
        int mid = (low + high) / 2;

        if (number > arrchange[high - 1]) {  //判断是否大于原数组最后一个元素
            return high;
        } else if (number < arrchange[0]) {  //判断是否小于原数组的第一个元素
            return 0;
        } else {
            while (low != high) {
                if(number == arrchange[mid]) {   //判断是否等于查找中间的元素
                    break;
                }else if(1 == high-low) {
                    break;
                }else if(number < arrchange[mid]) {
                    high = mid;
                    mid = (low + high) / 2;
                }else {
                    low = mid;
                    mid = (low + high) / 2;
                }

            }

            return mid+1;
        }

    }

}