2020--09--06 有序数组插入一个数

题目描述
有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，保证插入新数后，序列仍然是升序。
输入描述:
第一行输入一个整数(0≤N≤50)。

第二行输入N个升序排列的整数，输入用空格分隔的N个整数。

第三行输入想要进行插入的一个整数。

输出描述:
输出为一行，N+1个有序排列的整数。

解题思路：三种方法
1、插入到最后，然后通过sort排序再输出。
2、自己写排序，分三种情况：1)数组头部 2)数组尾部 3)数组中部
3、不储存在数组里面，有序数组在输出的时候进行判断，直接将给定的数在输出的时候显示，这时候控制好循环变量的自增就可以了。
参考思路：

参考代码：（第二种思路）

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String  str=input.readLine();//读取第一行的个数number
        int number = Integer.parseInt(str);
        str=input.readLine();//读取第二行的数组
        String[] values = str.split(" ");
        str=input.readLine();//读取第三行要插入的数字value
        int value = Integer.parseInt(str);
        int[] sample = new int[number];
        //sample是把字符串数组values转为int数组，也可以直接Integer.parseInt(values[0]),后面觉得可读性不强就改掉了
        int[] arr = new int[number+1];
        //arr是答案数组
        for (int i = 0; i < number; i++) {//sample数组初始化
            sample[i]=Integer.parseInt(values[i]);
        }
        if(value<=sample[0]){//第一个开头:如果value最小 放在最开头
            arr[0]=value;
            for (int j = 0; j < number; j++) {
                arr[j+1]=sample[j];
            }
        }
        else if(value>sample[number-1]){//第二个情况是结尾：如果value最大，先把sample的对应值给arr，再加入value
            for (int j = 0; j < number; j++) {
                arr[j]=sample[j];
            }
            arr[arr.length-1]=value;
        }
        else{//第三种情况如果在中间：当value大于左边小于右边的时候，插入数据
            arr[0]=sample[0];
            int index=1;//这里的index用来控制数组arr的下标，加入一个值后index自动加1，arr[index++]
            for(int i=1;i<number;){//遍历循环给答案数组加入值
                if(value<=sample[i]&&sample[i-1]<=value){
                    arr[index++]=value;
                }
                arr[index++]=sample[i];
                i++;
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

还没有达到最好的时间复杂度！！！