06 如何在一个有序数组中插入一个数据并使新数组保持有序(默认升序)

如何在一个有序数组中插入一个数据并使新数组保持有序(默认升序)

准备工作

import java.util.Scanner;
public class TestClass01 {
    public static void main(String[] args) {
        //在有序数组中插入一个元素,使得插入后所有的元素也保持有序,这里以升序为例
        int[] number={1,5,7,9};
        int[] number01=new int[number.length+1];//定义一个新数组,长度为老数组长度+!
        System.out.println("要插入元素的有序数组如下所示:");
        for (int i = 0; i < number.length; i++) {
            System.out.print(number[i]+"	");
        }
        System.out.println();
        System.out.println("请输入插入的数");
        Scanner scanner=new Scanner(System.in);
        int insert_number=scanner.nextInt();
    }
}

第一种 后移法

思路:

第一步:找到插入的下标

​ 分三种情况:

​ 第一种:当插入的元素值小于等于老数组的第一个值时,插入的下标为0

​ 第二种:当插入的元素值大于等于老数组的最后一个值时,插入的下标为数组长度

​ 第三种:正常进行注意部分的判断

第二步:把旧数组的插入下标之前的数据全部赋值给新数组

第三步:把插入的值赋值到新数组的插入下标的位置

第四步:把旧数组的插入下标以及之后的数据依次赋值给新数组插入下标+1及之后的位置(每次新数组接收都要加1)

  //第一种方法,后移法
        //第一步,先找到插入的位置
        int index=0;//定义一个变量存放插入的位置
        //从原数组里面找
        //有三种情况,第一种,插入的元素小于等于第一个元素,第二种情况在插入的数在中间位置,第三种情况为插入的数大于等于最后一个元素
        if(insert_number<=number[0]){
            index=0;   //第一种情况
        }else if(insert_number>=number[number.length-1]){
            index=number.length;//第三种情况
        }else{
            for (int i = 0; i < number.length-1; i++) {
                if(number[i]<=insert_number&&number[i+1]>=insert_number){
                    index=i+1;   //第二种情况
                    break;
                }
            }
        }
        //第二步,把老数组插入位置前的数据全部赋值给新数组
        for (int i = 0; i < index; i++) {
            number01[i]= number[i];
        }
        //第三步,把插入的值赋值给新数组的插入位置
        number01[index]=insert_number;
        //第四步,把老数组剩下的数据依次赋值给新数组插入位置后
        for (int i = index; i <number.length; i++) {
            number01[i+1]= number[i];
        }
        //第五步,验证:插入后排序
        System.out.println("输出插入数据"+insert_number+"后排序的数组如下所示");
        for (int i = 0; i < number01.length; i++) {
            System.out.print(number01[i]+"	");
        }

注意:插入下标应该满足:使得该位置的前一个数小于等于插入的数据,该位置的的后一个数大于等于插入的数据

第二种 插入位置放最后,然后两两比较

思路:

第一步:把旧数组的数据全部赋值给新数组的数据

第二步:把插入的元素放入新数组的最后一个位置

第三步:从新数组的末尾开始遍历整个新数组,如果当前位置的元素比前面一个位置的元素小,那么就把他们之前进行交换,交换完所有的之后就排序完成了.

  //第二种方法,放最后依次相比法
        //第一步,把老数组的元素全部赋值给新数组
        for (int i = 0; i < number.length; i++) {
            number01[i]= number[i];
        }
        //第二步,把插入的元素放入新数组的最后一个位置
        number01[number01.length-1]=insert_number;
        //第三步,从新数组的最后一个元素起开始遍历整个,数组
        // 若当前位置的元素比前面一个元素的值小,则进行两两交换
        //直到遍历结束,此时新数组排序已经成功
        for (int i = number01.length-1; i>0; i--) {
            //比它小就互换,因为是升序,遍历到第一个元素的时候就不需要比较了,所以i无需等于0
           if(number01[i]<number01[i-1]){
               int temp=number01[i];//定义一个临时变量用来进行数据交换
               number01[i]=number01[i-1];
               number01[i-1]=temp;
           }
        }
        //第四步,验证是否排序成功
        System.out.println("输出插入数据"+insert_number+"后排序的数组如下所示");
        for (int i = 0; i < number01.length; i++) {
            System.out.print(number01[i]+"	");
        }