Python|关于简单插入排序的奥秘

前言

相信大家在生活中经常会遇到排序的问题，比如，如果你是超市工作人员，看到货架上的货品被顾客弄乱了，你一定会重新给货品排序，基本上是按从小到大、从矮到高的顺序摆放。在家里面，你也一定会给家里的物品按照自己喜欢的顺序进行摆放。在公司里，如果有大量文件，你也会按时间、按文件名、按大小等等的方式给这些文件进行整理。当然还有很多这样的情况，那么我们为什么要进行排序呢？排序不会浪费我们的时间吗？其实不然，排序是为了让东西更有连续性，或者更有规律性，能够方便我们的下一次使用，快速找到自己想要的东西，所以排序并不会浪费我们的时间，相反还会节约我们的时间。那么在计算机中，也有排序哦！在计算机里面的排序则是为了让数据更加具有结构性，方便计算机对其处理。而小编今天想要分享的是：简单插入排序。

问题描述

把下面的打乱顺序的数，按照从小到大的顺序进行排列【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)，与序列大小无关。但是如果数据过多，我觉得这个算法就显得很麻烦，最坏的情况下，其复杂度为

,这就是它的局限性。那么我们可不可以对它进行变形使之变得更简单点呢？当然有啦，那就是小编下次想讲的二分法查找。如果感兴趣，记得点赞收藏哦。

作者：刘欣

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）