排序

它是什么

排序就是让一列东西按约定方向排队。可以按大小、高矮、学号、姓氏笔画。

比较是排序的第一步。每次先看两个，谁在前、谁在后，或是否并列，再把这种判断推广到整列。

从小到大，叫升序，像爬楼梯，一格比一格高。例如：138、142、145、150、150。

从大到小，叫降序，像发奖牌，高的在前。例如：150、150、145、142、138。

方向没说清，队就会全反。相等不是失败：身高相同、分数并列，都合法。并列时，相同的数应紧挨着。

名字从哪来

人很早就在排队。士兵按身高，字典按字母，图书馆按索书号。索书号是书架上的地址：同一类书挨在一起，号码小的常常在前。你按号找书，就是在走一条已经排好的路。

电脑里的排序，名字很多。有一种常被讲成故事，叫冒泡：把数当成站成一排的同学，从左到右，相邻两个比高矮；如果顺序反了，就交换位置。矮的会一格一格往左「冒」过去。走完几轮，整队就顺了。

你不必会写这种程序。先明白：排序就是反复比较、必要时交换。人手排五个数，已经在做同一件事。

它怎么工作

先看清方向。「从矮到高」是升序，「从高到矮」是降序。

比较时常见五种说法：

小数先比整数部分。整数相同，再比十分位、百分位。9.8 大于 9.75。

怎么判断一列有没有排好？从左往右，只看相邻两项。

3、5、5、9：每一步都是变大或持平，这是升序。

8、8、6：持平后变小，这是降序。

9、7、8、2：先变小，再变大，中途掉头。既不是升序，也不是降序。

口诀：一路不回头，才算排好队。

冒泡的故事可以这样想：每一轮只解决相邻的错位，像气泡在水里一格格升上去。数很多时，人会累，电脑不怕重复比较。

排好以后，最大值和最小值 就在两端。升序最左边是最小，最右边是最大。

生活里在哪里

• 成绩榜、跑步名次
• 按学号、座位号排列
• 图书馆索书号：按号码在书架上走
• 通讯录按姓氏
• 网购按价格从低到高

排好序以后，更容易找中等水平，也更容易发现离谱的数。找整体水平，还要看 平均数。排序帮你看队伍，平均帮你看整体。

电脑查找前，常常先排序。有序的名单，折半去找会更快。那是以后的事。现在先练：五个数，能排对，能看出有没有掉头。

和相近概念的差别

顺序流程 管「先洗衣再晾衣」，排序管「谁的数更大」。一个是步骤次序，一个是大小次序。

按 特征 排序时，先约定按哪一列。按身高排和按学号排，队伍会不一样。

常见误会

误会 1：只看首尾，不看中间。

中间一掉头，就不是有序。

误会 2：把两个相同的数拆开插到别处。

并列应当紧挨着。

误会 3：升序降序搞反。

先把方向读成一句人话：从矮到高，还是从高到矮。

误会 4：比较小数时只看位数多少。

9.8 比 9.75 大。不是位数多就更大。

想知道更多

• 活动：CS Unplugged《不插电的计算机科学》里有「排序网络」：同学站在绳网交叉点上比高矮，身体就能完成排序。
• 纪录片：法国片《维度：数学漫步》（Dimensions）。位置和次序在空间里也会被排好。
• 生活作业：把家里五本书按书名首字拼音或按厚薄排一次。请别人检查：有没有中途掉头。