常用排序算法-直接插入排序

介绍

直接插入排序算法是一种简单，直观且稳定的排序算法。直接插入排序的基本思路是将一个元素插入到已经排好序的序列中，从而得到一个新的有序序列。

原理

直接插入排序的原理就好比抓扑克牌一样，我们每新抓到一张扑克后，会扫描已经有序的扑克牌，以升序为例，从大到小扫描扑克牌，当出现扑克小于当前的新扑克时，将新扑克牌插入到该牌的后面，即可得到一个新的有序序列。

以[6,2,5,8,7]为例可以将数组分为两个子集，其中左子集是有序的，而右子集是待插入元素，当子集中只有一个元素时，显然是有序的。我们将2插入到有序子集中，6大于2，则将6向后移动一个位置，此时有序子集中的元素都比新元素2大，则将2插入到前面，实际上就是索引为0的位置，依次将右子集的元素插入到有序子集中，最终会得到一个排好序的数组。

程序

public class InsertSort {
    public static void insertSort(int[] arr){
        if(arr == null || arr.length == 0)
            throw new IllegalArgumentException("error");
        for(int i = 1; i < arr.length; ++i){
            int index = i - 1;
            int insertNum = arr[i];
            while(index >= 0 && arr[index] > insertNum){
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = insertNum;
        }
    }
}

总结

直接插入排序的时间复杂度最差为O(n^2)，最好情况时O(n)，平均时间复杂度为O(n^2)。

同时直接插入排序是在原数组上直接进行操作，空间复杂度是O(1)。

由于直接插入排序的原理，后面的元素插入到已排序数组中，若遇到相同元素则直接放在后面，不难推断出是稳定的。