Java八大排序算法之插入排序介绍
发布时间：2021-11-12 10:39:41 所属栏目：教程 来源：互联网
导读：八大排序算法之插入排序（动图演示 思路分析 实例代码Java 复杂度分析） 一、动图演示 二、思路分析 例如从小到大排序: 1. 从第二位开始遍历， 2. 当前数（第一趟是第二位数）与前面的数依次比较，如果前面的数大于当前数，则将这个数放在当前数的位置上，当
|
八大排序算法之插入排序（动图演示 思路分析 实例代码Java 复杂度分析） 一、动图演示 二、思路分析 例如从小到大排序: 1. 从第二位开始遍历， 2. 当前数（第一趟是第二位数）与前面的数依次比较，如果前面的数大于当前数，则将这个数放在当前数的位置上，当前数的下标-1， 3. 重复以上步骤，直到当前数不大于前面的某一个数为止，这时，将当前数，放到这个位置， 1-3步就是保证当前数的前面的数都是有序的，内层循环的目的就是将当前数插入到前面的有序序列里 4. 重复以上3步，直到遍历到最后一位数，并将最后一位数插入到合适的位置，插入排序结束。 根据思路分析，每一趟的执行流程如下图所示： 三、复杂度分析 1. 时间复杂度：插入算法，就是保证前面的序列是有序的，只需要把当前数插入前面的某一个位置即可。 所以如果数组本来就是有序的，则数组的最好情况下时间复杂度为O（n） 如果数组恰好是倒=倒序，比如原始数组是5 4 3 2 1，想要排成从小到大，则每一趟前面的数都要往后移，一共要执行n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n2 - 0.5 * n次，去掉低次幂及系数，所以最坏情况下时间复杂度为O（n2） 平均时间复杂度(n+n2 )/2，所以平均时间复杂度为O（n2） 2. 空间复杂度：插入排序算法，只需要两个变量暂存当前数，以及下标，与n的大小无关，所以空间复杂度为：O（1） 四、Java 代码如下 import java.util.Arrays; public class insertSort { public static void main(String[] args) { int[] n = new int[]{20,12,15,1,5,49,58,24,578,211,20,214,78,35,125,789,11}; int temp = 0,j; for (int i = 1; i < n.length; i++) { temp = n[i]; for (j = i; j >0; j--) { //如果当前数前面的数大于当前数，则把前面的数向后移一个位置 if(n[j-1]>temp){ n[j] = n[j-1]; //第一个数已经移到第二个数，将当前数放到第一个位置，这一趟结束 if(j==1){ n[j-1] = temp; break; } }else{//如果不大于，将当前数放到j的位置，这一趟结束 n[j] = temp; break; } } System.out.println(Arrays.toString(n)); } System.out.println(Arrays.toString(n)); } }  （编辑：开发网_开封站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330459号