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]+"\t"); } 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]+"\t"); }
注意:插入下标应该满足:使得该位置的前一个数小于等于插入的数据,该位置的的后一个数大于等于插入的数据
第二种 插入位置放最后,然后两两比较
思路:
第一步:把旧数组的数据全部赋值给新数组的数据
第二步:把插入的元素放入新数组的最后一个位置
第三步:从新数组的末尾开始遍历整个新数组,如果当前位置的元素比前面一个位置的元素小,那么就把他们之前进行交换,交换完所有的之后就排序完成了.
//第二种方法,放最后依次相比法 //第一步,把老数组的元素全部赋值给新数组 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]+"\t"); }
赞 (0)