插入排序

（Insertion sort）

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

思路

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

重点：使用哨兵，用于临时存储和判断数组边界。

例如从小到大排序:

1. 从第二位开始遍历，

2. 当前数（第一趟是第二位数）与前面的数依次比较，如果前面的数大于当前数，则将这个数放在当前数的位置上，当前数的下标-1，**
**

3. 重复以上步骤，直到当前数不大于前面的某一个数为止，这时，将当前数，放到这个位置，

1-3步就是保证当前数的前面的数都是有序的，内层循环的目的就是将当前数插入到前面的有序序列里

4. 重复以上3步，直到遍历到最后一位数，并将最后一位数插入到合适的位置，插入排序结束。

根据思路分析，每一趟的执行流程如下图所示：

动态效果

代码

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {

        int arr[] = {2,1,5,3,6,4,9,8,7};

        int temp;

        for (int i=1;i<arr.length;i++){

            //待排元素小于有序序列的最后一个元素时，向前插入
            if (arr[i]<arr[i-1]){
                temp = arr[i];
                for (int j=i;j>=0;j--){
                    if (j>0 && arr[j-1]>temp) {
                        arr[j]=arr[j-1];
                    }else {
                        arr[j]=temp;
                        break;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));

    }


}

算法

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）