找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法一看就懂之「 插入排序 」

admin 2019-11-7 20:36 121人围观 C++相关

上一篇文章咱们已经聊过「 冒泡排序 」了,今天咱们来看一看「 插入排序 」。「 插入排序 」与「 冒泡排序 」一样都属于时间复杂O(n*n)的排序算法,并且也都是基于元素之间比较的方式来完成排序的。不过「 插入排序 」比「 冒泡排序 」在实际应用中更广泛一些,因为它的执行效率更高一点。

一、「 插入排序 」是什么?


插入排序 是一种最简单的排序算法,它的思路是将一组待排序的数据,分成2段,一段是“已经排序”了的数据,另一段是“未排序”的数据。只要每次都从“未排序”的数据中取出一个元素,将这个元素插入到“已经排序”数据中的正确的位置(可能会涉及到原有元素的移动),那么插入后,“已经排序”区段中的数据依然是有序的,只要这样不停的循环,直到所有的“未排序”的数据都已取完,则整个排序完成。



这个原理很像大家平时娱乐时打的扑克牌,在每一局开始的取牌阶段,每取一张牌,就将这张牌插入到手中那些已排好的牌中的正确位置,直到所有的牌取完。

下面用一个整数数组做一个示例:
初始状态836279移动次数
第一遍3862791
第二遍3682791
第三遍2368793
第四遍2367891
第五遍2367890

上述示例中,初始数组是 8,3,6,2,7,9,在初始状态时,我们将将数组分为2个段,第一个元素8当做是“已经排序”了的区段,后面所有的元素是作为“未排序”的区段。然后我们开始循环,依次拿出后面“未排序”的区段中的元素与“已经排序”了的区段进行比较,并找到合适的位置插入。

  1. 第一遍循环时,从“未排序”的区段中拿出元素3,它比“已经排序”段中的元素8小,因此需要将元素8向后移动一位,留出空位让元素3插入。这次只需要移动一个元素,表中也标注了移动次数为1次。

  2. 第二遍循环时,从“未排序”的区段中拿出元素6,它比“已经排序”段中的元素3大、比元素8小,因此元素3不动,只需要将元素8向后移动一位,留出空位让元素6插入,这次移动次数也为1次。

  3. 第三遍循环时,从“未排序”的区段中拿出元素2,它比“已经排序”段中的元素2小,因此需要将元素3、元素6、元素8均向后移动一位,留出空位让元素2插入,这次移动次数为3次。

  4. 第四遍循环时,从“未排序”的区段中拿出元素7,它比“已经排序”段中的元素6大、比元素8小,因此需要将元素8向后移动一位,留出空位让元素7插入,这次移动次数为1次。

  5. 第五遍循环时,从“未排序”的区段中拿出元素9,它比“已经排序”段中的元素8大,因此“已经排序”的区段无需移动,直接在最后的位置将元素9插入,这次移动次数为0次。

说再多都不与看代码来得直接,下面我们来看一个插入排序的代码:
    算法题:对数组arr进行从小到大的排序,假设数组arr不为空,arr的长度为n思路:采用插入排序方法
    public void inertSort(int[] arr){ int i,j; int n = arr.length; for(i=1; i<n; i++){ //位置0是“已经排序”区段,因此从位置1开始,依次取出“未排序”区段的元素 int needSort = arr[i]; //在“已经排序”区段中,从后往前循环,对比needSort for(j=i-1; j>=0; j--){ //如果needSort小于arr[j],则说明需要将arr[j]往后移动一位,以便留出空位 if(val < arr[j]){ arr[j+1] = arr[j]; }else{ break; } } //将元素放入到正确的位置 arr[j+1] = needSort; }}

    二、「 插入排序 」的性能怎么样?


    我们按照之前文章中讲到的排序算法评估方法来对「 插入排序 」进行一下性能评估:

    • 时间复杂度:

      插入排序原理就是在两层嵌套循环里进行对比,所以简单来讲,其一般情况下的时间复杂度就是O(n*n)了。但如果仔细去分析的话,就得看具体的数据情况,如果待排序的数据本身就是有序的,那么我们只需要做外层循环就可以(因为内层循环每次都是一开始就判定不成立而立即终止),此时就是最好的情况,其时间复杂度为:O(n),但如果待排序的数据全部都是逆序的,那我们在每次内循环中都需要做大量的移动数据的操作,其最坏情况下,时间复杂度就是:O(n*n)了。

    • 空间复杂度:

      插入排序完全就是移动数据,只需要一个辅助空间用来存储待比较的元素,并没有消耗更多的额外空间。因此其空间复杂度是O(1)。

    • 排序稳定性:

      在本系列的最开始介绍过了排序算法稳定性的定义,这里不重复介绍了。对于插入排序,在做元素对比的时候,如果元素大小相同,则可以将后面的元素插入到当前元素的后面,这样就可以保证它们原有的相对位置不变了,因此它是排序稳定的。

    • 算法复杂性:

      插入排序的算法无论是其设计思路上,还是代码的编写上都不复杂,其算法复杂性是比较简单的,可以说插入排序是最简单的排序算法之一了。

    以上,就是对数据结构中「 插入排序 」的一些思考,您有什么疑问吗?

    END

    Java面试题专栏

    【01期】Spring,SpringMVC,SpringBoot,SpringCloud有什么区别和联系?

    【02期】你能说说Spring框架中Bean的生命周期吗?

    【03期】如何决定使用 HashMap 还是 TreeMap?

    【04期】分库分表之后,id 主键如何处理?

    【05期】消息队列中,如何保证消息的顺序性?

    【06期】单例模式有几种写法?

    【07期】Redis中是如何实现分布式锁的?

    【08期】说说Object类下面有几种方法呢?

    【09期】说说hashCode() 和 equals() 之间的关系?

    【10期】Redis 面试常见问答



    欢迎长按下图关注公众号后端技术精选




    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:后端技术精选,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......