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

介绍

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

原理

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

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

初始数组6 2578
第一趟26 578
第二趟256 78
第三趟2567 8
第四趟25678 

程序

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)。

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

相关推荐