直接插入排序

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_44026997/article/details/89001904
直接插入排序
1.原理：

把n个待排序的元素看成一个有序表和一个无需表，开始的时候有序表只有1个元素，无序表中有n-1个元素

每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

2.实例：

0.初始状态 3，1，5，7，2，4，9，6（共8个数）
有序表：3；无序表：1，5，7，2，4，9，6
1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序
有序表：1，3；无序表：5，7，2，4，9，6
2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5；无序表：7，2，4，9，6
3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5，7；无序表：2，4，9，6
4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，5，7；无序表：4，9，6
5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7；无序表：9，6
6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7，9；无序表：6
7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，6，7，9；无序表：（空）

3.效率分析：

稳定

空间复杂度O(1)
时间复杂度O(n2)

最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素

数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；

插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。

通常，插入排序呈现出二次排序算法中的最佳性能。

4.代码：

public class InsertSort {
    public static void insertSort(int[] arr){
        int j = 0;
        int temp = 0;//临时变量
        for(int i = 1;i < arr.length;i++){//从第二个数开始比较
            temp = arr[i];  //将当前数插入到已经有序的数组中
            for(j = i - 1;j >= 0;j--){
                if(arr[j] > temp){//如果前面的数大于当前数，将他后移
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = temp;//将当前轮数的数放到应该在的位置
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args) {
        int[] arr = {1,32,2,12,33};
        insertSort(arr);
    }
}