十大排序算法之插入排序

╰+攻爆jí腚メ 2024-04-18 06:24 74阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。  
思路：  
就像在书桌上排列大小不同的书籍，大的放右边，小的放左边  
首先我们确定第一个数是固定的，然后我们取出第二个数与第一个数比较，  
比它大就放在它的右边，比它小就放在它的左边，  
然后取出第三个数，与最大的数比较，比它大就放在它的右边，比它小就与前边一个数比较，  
直到遇到一个比它小的数。  
阻碍：  
当我们找到位置后，无法控制数组给新来的数据让出位置，  
有两种解决方法，  
设新数据找到的位置为x，原来位置为y；  
一，找到位置x后，把新数据提取到一个变量上，  
从x到y-1所有数据用交换变量的方式向后移一位，  
这个方法比较耗时。时间复杂度O（n3）  
二，在寻找位置的过程中随时交换变量，以冒泡的方式移动  
时间复杂度O（n2）  
执行：  
外层循环用来确定数组中的每一个数的位置  
内层循环用来寻找当前数的所在位置，并时刻移动当前数![在这里插入图片描述][20190903152026101.gif]  
评价：  
需要开辟的空间约等于0；  
时间复杂度为O（n2）

import java.util.Arrays;
    
    public class 插入排序 {
    	public static int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    
    	public static void main(String[] args) {
    		//从第二项开始抽取，选择位置进行插入
    		for (int i = 1; i < a.length; i++) {
    			//将元素抽取出来
    			int t = a[i];
    			//	定义变量j用于记录下标		
    			int j;
    			//遍历当前抽取的元素 之前的元素，如果所经历的元素恰好大于抽取的元素，把经历的元素后移一位
    			for (j = i - 1; j >= 0 && a[j] > t; j -= 1) {
    				a[j + 1] = a[j];//把元素赋值给后边元素
    			}
    			//当所经历的元素小于当前元素时，会跳出循环，我们把取出的元素放在这个位置的右移一个位置即可
    			a[j + 1] = t;
    		}
    		System.out.println(Arrays.toString(a));
    	}
    }

[20190903152026101.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9fed18c91fbb4e7bb199b401e486f3e3.gif