文章首发：微信公众号【九粽】

大噶好！转眼间我们上班的上班，上学的上学，相信已经有一阵子了。

面对工作中要处理的花花绿绿的数字，我们最常用的操作可能就是——花里胡哨看不出来什么，要不先排个序吧。

​

咔咔一点，数据排好了序，仿佛是等待你检阅的士兵。

排序——自古以来就是非常实用的一个理清事物的方法。比如早操排队会按高矮排序，史料记载会按时间排序，单词查找会按字母排序，YB国会按沙雕程度排序（国王第一，其余全部并列第二）。

计算机世界也是一样，对排序有着强烈的执念。既然有了这个需求，下面就是怎么办的问题了。

注意：阅读本文不需要任何计算机知识，相反的，阅读本文过后你会具备一些计算机常识。

现在，你前面站着一排小学生准备做早操，首先需要你想办法把他们从矮到高排成一列，下面的数字代表小学生的高度：

7，6，9，8，5，1 （不要在意“1是多高”这种细节）

为了彰显我本人的聪明才智，排序后正确答案我现在就给出来，是1，5，6，7，8，9。

此刻我相信，家里有体育老师经常给学生排队的，在这个问题上应该不输给数学老师。一下子映入脑海的可能就有以下几种方案。

方案一：你也许会说，这个简单，我先一眼揪出那个最高的，然后把他直接放到最后面。再在剩下的里面揪出最高的，排在倒数第二个……依次类推。

这个方法非常直观，并且有效。每次选择出一个最高的，在计算机里面的名词也很直白，就叫选择排序。

问题来了，如果有1000个学生，一眼望不到头。那么这是体育老师就要和数学老师合作了：体育老师从头跑到尾，看当前谁是最高的；数学老师站在队尾，告诉体育老师他刚才已经记到哪儿了。

【亲爱的，我跑了一趟，这个最高！】

【么么哒，把这学生交给我吧，你去看看剩下的谁最高】

【亲爱的，我又跑了一遍，现在这个最高！】

【么么哒，这是第二高的学生，你再去看看剩下的】

……

【亲爱的，我又跑了一遍，现在排到哪儿了？】

【我这里有233个排过序的了，你再跑一遍看剩下谁最高】

……

最后排队成不成功我不知道，但是体育老师估计是要累死了。

方案二：体育老师站了出来，mmp劳资不跑了！全体都有！我吹一声哨子，每个人就跟前面的人比比个子，要是前面的人高，你就跟他换一换！

㘗（qū）一声哨响，个子矮的人往前换了换；

又一声哨响，个子矮的人又往前换了换；

……

最终，个子最矮的那个小朋友站在了队伍最前面。

这个最矮的小朋友，每次前进一位，就像小鱼儿吐出的泡泡，Bububu的一点一点浮到了水面上（就是队伍最前面）。这种自底而上的挪动过程，计算机算法的名字也很直白，叫冒泡算法。

问题又来了，如果有1000个小朋友等待排队，这时候体育老师会怎么吹哨呢？

【㘗！——】过了一会儿，最矮的小朋友排到了第一个；

【㘗！——】又过了一会儿，第二矮的小朋友也浮到了队伍前面，跟第一位比了比之后，排在了第二个。

……

【㘗！——】第299次哨响过后，前几名的小朋友哭了：【老师，我们的位子早就固定了，别让我们每次都比较了吧？】

【这可咋办呢？……】这个问题涉及到了体育老师的知识盲区。

【亲爱的我来帮你吧】关键时刻还是数学老师挺身而出，【你第一次吹哨，说明第一个小朋友就已经排好了。这样，跟刚才一样，你每次吹完哨我都帮你数着，那前面的小朋友们就不用再比较了】

【亲爱的你可真聪明！】体育老师眼角泛起了泪花。

【就一点小忙，不用感动到落泪……】

【不是感动，是我tm吹了1000次哨子，哨子牺牲了……】

方案三：得，这下体育老师哨子也没了，还是得跑。不过我们似乎可以在方案一的基础上改进一下。

（别告诉你已经忘记方案一是啥了……）

之前体育老师每次都要从头到尾跑，找出最高的小朋友。

现在让他省省劲儿：数学老师那儿不是已经排好队了嘛，体育老师提起一个没排队的小朋友走到数学老师的队里。

从前往后走，边走边跟手上的小朋友比较。

找到合适的地方就把小朋友往那儿一放就行，不用往后走了。

搞事的那1000个小朋友又来了……

【亲爱的，这是第一个小朋友，放你这儿。】

【这是第二个小朋友，让我看看……你比第一个小同学高，你就排他后面吧】

【这是第三个小朋友，嗯…你比第一个高，但比刚才第二个矮，你就排中间吧…】

……

【这是第666个来排队的小朋友，在排好队的同学里…我瞅瞅…你比前100名高，但比101名矮，那你就排100的后面吧】

就这样，虽然每次体育老师还是要跑来跑去，但是每次点到为止，不需要从头跑到尾。这种每次提着小朋友插♂入到合适位置的方法，计算机语言同样直白，就叫插入算法。

到这里为止，各位已经明白了计算机三大简单排序算法，可以给自己鼓个小掌以示鼓励，或者点一顿烧烤作为奖励。

不过这几个方法的弊端也是显而易见的：

（1）一定要数学老师和体育老师合作；

（2）体育老师总是累得要死要活。

如果把体育老师换成一个别的老师，可能光是跑来跑去就要耗费不少时间，为了彰显体育老师的特长，在计算机里，我们总得有个酷炫的名词来衡量一个方法花了多少时间，它就叫 时间复杂度。

那上面几个方法都花了多少时间呢？我们再把那1000个小朋友拉出来。

——首先，数学老师手里的学生一开始没有，然后越来越多，每次增加一个已经排好队的学生。

——每当数学老师手里增加一个排好队的学生，就意味着这是体育老师跑遍了剩下的学生，为她找出来的。

——那这时间就是1000*1000 （四舍五入就是一个小目标啊）

——体育老师的这种舍己为人，无私奉献的精神，我们称之为 舔狗精神 白求恩精神。

——虽然体育老师后来改进了，不用全都跑，但如果人数特别特别多，他节省的时间比起巨大的数据量，可以忽略不计。

——即，以上算法的时间复杂度都是n²。

还能不能给体育老师一点活路？……

直到1959年，有一个叫Shell 的人横空出现，提出了一个划时代的方案……

你是不是那个Shell？