前言
相信大家在生活中经常会遇到排序的问题,比如,如果你是超市工作人员,看到货架上的货品被顾客弄乱了,你一定会重新给货品排序,基本上是按从小到大、从矮到高的顺序摆放。在家里面,你也一定会给家里的物品按照自己喜欢的顺序进行摆放。在公司里,如果有大量文件,你也会按时间、按文件名、按大小等等的方式给这些文件进行整理。当然还有很多这样的情况,那么我们为什么要进行排序呢?排序不会浪费我们的时间吗?其实不然,排序是为了让东西更有连续性,或者更有规律性,能够方便我们的下一次使用,快速找到自己想要的东西,所以排序并不会浪费我们的时间,相反还会节约我们的时间。那么在计算机中,也有排序哦!在计算机里面的排序则是为了让数据更加具有结构性,方便计算机对其处理。而小编今天想要分享的是:简单插入排序。
问题描述
把下面的打乱顺序的数,按照从小到大的顺序进行排列【1,3,5,22,4,11,55,66,40,7】
解决方案
插入排序,核心内容就是插入,即将一个个元素插入到序列中,最后得到自己想要的有序序列。这就是一个从无序到有序的过程。
看这题,我们先将1作为第一个元素,然后将3与它比较,3>1,则插在1后面;再将5与3比较,5>3,则插在3后面,同理22插在5后面。重点来了:4于22比较时,4<22,则往前插入,插在22前,再与5比较,4<5,又继续往前插入,插在5前面,再与3比较,这个时候因为4>3,所以停止插入。后面的排序与上面同理。就是比前一个数小,就向前插入,直到遇到比自己还小的数停止。所以最后的排序是【1,3,4,5,7,11,22,40,55,66】
结语
简单插入排序是一种很基础的算法,因为只用了两个简单变量,所以空间复杂度为O(1),与序列大小无关。但是如果数据过多,我觉得这个算法就显得很麻烦,最坏的情况下,其复杂度为
,这就是它的局限性。那么我们可不可以对它进行变形使之变得更简单点呢?当然有啦,那就是小编下次想讲的二分法查找。如果感兴趣,记得点赞收藏哦。