排序—插入排序

清溪算法君老号 2020-06-06

许久没有写点东西了,答辩之后人也变得松懈。今天看到简书又有人点赞之前记录的冒泡排序,点进去一看,居然有4w+的阅读量,心生疑问,咋会有这么高的阅读量,打开百度搜索冒泡排序,结果第3条就是我的。点开认真看了看,其实写得不好,还改了两个错别字(狗头),这个阅读量或许只是记录的点击量。但我萌生一个想法,趁现在有时间,想把排序系列做完,便于以后自己回顾。

排序系列传递门

排序—冒泡排序
排序—选择排序
排序—快速排序
排序—插入排序
排序-希尔排序(待完善)
排序—归并排序(待完善)
排序—基数排序(待完善)
排序—堆排序(待完善)
排序—桶排序(待完善)
排序—计数排序(待完善)
排序—排序算法总结(待完善)

插入排序思想

基本思想是在一个有序的序列中找到待排序元素的位置,比如将3插入-1,2,4,6这个有序序列中,先与6和4比较,直到和2比较之后,找到适合插入的位置(2之后)。
下面以按升序排序为例:

  • step1 第一个元素默认有序。
  • step2 取待排序的元素B,在有序序列上从后往前寻找。
  • step3 如果已排序元素A大于待排序的元素B,则将A往后移动一位。
  • step4 重复step3,直到找到元素A<=B(待排序)时或者有序序列全部被扫描。将待排序元素A插入。
  • 重复step2—step4

动图展示(图片来源见参考资料)
排序—插入排序

代码实现(java)

/**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        if(arr == null || arr.length == 0) 
            return;
        int curEle, preIndex; // 记录当前待排序元素和前一个元素的下标
        for(int i = 0; i < arr.length; i++) {
            preIndex = i - 1;
            curEle = arr[i];
            while(preIndex >=0 && arr[preIndex] > curEle){
                arr[preIndex + 1] = arr[preIndex]; // 移动元素
                preIndex--;
            }
            // 将待排序元素插入新的位置
            arr[preIndex + 1] = curEle;
        }
    }

算法分析

时间复杂度:$O(n^2)$
空间复杂度:$O(1)$
稳定性:稳定

参考资料

值得收藏的十大经典排序算法

最后

本文若有不当,请指出。
此致,敬礼!

相关推荐

yuanran0 / 0评论 2020-04-20
闫新宇 / 0评论 2015-02-06