排序算法 怎么工作

什么是排序

让大家按个子排队，一开始总是乱七八糟的。
排序就是把它们从小到大按顺序排好。
在下面可以比较一下乱的样子和排好的样子。

乱七八糟 vs 排好的样子。乱七八糟 → 从小到大。

排好的队伍看着就舒服。
但更重要的是，有了顺序，以后找起来就容易。
就像字典按字母顺序排列，想找的词很快就能查到。

和旁边的人比个子

怎样排队呢？
诀窍非常简单：看相邻的两个，左边的大就交换位置。
小的往前，大的往后，就这一个动作。

左边大就交换位置。比较两个 → 大的往后。

每次只比较两个。
一次两个，大了就换，小了就不动。
不用费脑子，只是不停地重复这个简单的动作。

大的往后走

现在来真正排一排。
从左边开始，相邻的两两比较，把大的往后推。转完一圈，最大的就落到了最后面。
这样反复做，队伍就一点点排好了。
按“开始排序”，就能看到这个过程。

反复比较和交换。黄色=正在比较 · 红色=正在交换 · 绿色=已就位。

能看到大的柱子像气泡一样浮到后面去。
每转一圈，就有一个找到自己的位置。
简单的比较和交换积累起来，就排成了完整的队伍。

为什么最后一定能排好

每转一圈，剩下的最大的就落到后面。
转两圈，第二大的就位；转三圈，第三大的就位。
就这样每一步从后面填好一个，步数足够了，总会全部排好。

每按一次“再走一步”，就有一个就位，步数够了，队伍就排完了。

所以排序是靠得住的。
不管多乱，只要一步步走下去，队伍一定能排好。
不管快慢，只要守住顺序，结局就是确定的。

排好队的好处

排序到处都有。
按分数排名次，按字母顺序列名字，按价格展示商品。
最重要的是，排好了队，找东西就容易多了。这是稍后要讲的故事。

排好了队，接下来。排序 = 按顺序排好 → 查找 · 排名 · 更远处。

排队这件事本身就有用，也是为下一步做的准备。
整理好了，找起来、挑起来都容易。
顺序的力量比想象的大。