[插入排序]-java实现插入排序

2021/10/21 17:11:12

本文主要是介绍[插入排序]-java实现插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序思想:将n个待排序的元素看成一个有序表和一个无序表,开始时,有序表中只有一个元素,无序表中有n-1个元素,排序时,每次从无序表中取出第一个元素,把它依次与有序表中元素进行比较,将它插入到有序表中的适当位置,使之最后成为一个有序表。
编程思想:一般初始有序表就是arr[0],循环遍历设置待插入的数arr[i] 和它想插入的位置 i-1。
时间复杂度:O(n²)

public int[] insertSort(int [] arr){
	for(int i=1; i < arr.length ; i++){
		int insertVal = arr[i];	//待插入的值为arr[i]
		int insertIndex = i -1; // 待插入的位置,插到有序表前一位
		
		// 待插入的值想一直往前插,要确保大于有序表中数据,且不能越过0
		while( insertInde >=0 && insertvalue < arr[insertIndex]){
			//一旦条件成立,有序表中元素后移,待插入的地方继续向前找
			arr[inserIndex+1] = arr[insertIndex];
			insertIndex --;
		}
		//一但跳出循环,说明已经找到了待插入的索引,不好想的话就想是插到末尾。索引得1+1
		arr[insertIndex+1] = insertVal;
	}
	return arr;
}



这篇关于[插入排序]-java实现插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程