一、动图演示

 

 

二、思路分析

例如从小到大排序:

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 * n ^ 2 – 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[]{1,6,3,8,33,27,66,9,7,88};
        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];
                }else{//如果不大于，将当前数放到j的位置，这一趟结束
                    n[j] = temp;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(n));
    }
}

 

版权声明：本文为l199616j原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/l199616j/p/10594363.html