居家隔离的带娃攻略 | 邮件排序 | Bad of Choices

居家隔离的带娃攻略 | 邮件排序 ... 版权说明：《Bad Choices》是由Ali Almossawi著作的一套计算思维书籍，可以通过https://bookofbadchoices.com/访问本书英文版本。书中通过一系列人物的故事场景，以插画的方式展示了一个个现实生活中遇到的问题，进而引出了一些计算思维的问题，内容丰富且非常有趣。本书的目标读者是计划学习编程的儿童、学生，通过阅读本书可以开拓眼界，培养计算思维习惯。

本章背景故事（请孩子阅读，家长伴听）

居家隔离的带娃攻略 | 小C是一名邮递员，今天他的工作已经发生了延迟。在太阳暴晒的七月中，在外面哪怕走一小会儿也能让你汗流浃背，更何况他今天穿的是标准的公司制服。更糟糕的是，作为一个心不在焉的邮递员，他刚刚打翻了箱内原本已经分门别类的邮件，把原本要投递的三十三个私人信件都混在一起了。屋漏偏锋连夜雨，他那敏感的皮肤已经开始刺痛并提醒他，“你把防晒霜忘在家里了！”。他跪在灼热的柏油马路上，捡起邮件，试图在他的皮肤受伤之前尽快把所有东西都整理好。

提示：考虑如何将问题分解为更小的问题，顺序可以帮助我们高效完成。想象一下，如果一份报纸没有按天列出本地发生的事件，或者如果你打算观看的电视剧没有按顺序列出，花时间翻找下一集是多么令人讨厌。

让我们描述一下小C如何着手解决他眼前的困境。

目标：按正确的顺序放回散落的信件。

方法一：在他面前的地上放一封信，拿起第二封并和第一封做比较，如果地址更近，把它放在第一封的左边。依此类推，直到最近的地址在该行的左侧，而最远的地址在该行的右侧。

方法2：把这堆信排成一行，在中间进行分割，然后在对每一边进行继续分拆，依此类推，分成很多组。对于每组中的信件，将较近的地址放在左侧，将较远的地址放在右侧，然后对每一组都这样做，依此类推。

两种方法的时间曲线如上所示，考虑一下哪种快以及原因？

思考完成再接着往下看哦！

居家隔离的带娃攻略 | 邮件排序 | 分析过程（请家长+孩子分段阅读思考）

在现实生活中，每当我们手动对许多东西进行分类时，就像小C在这种情况下一样，我们可能会使用方法 1 的一些类似方法。正如我们目前在比较图中看到的那样，在一些数量较少的情况下，任何完成手头任务的方法都可能是好的；只有当项目数量增加时，一种方法才可能会明显优于另一种方法。虽然方法 2 在现实生活中可能没有实际的应用体验和推论——至少在排序方面——我们将在概念上讨论它的一般方法。

首先请注意，方法 1 有一定的韵律重复的节奏。小C拿了一封信，然后查看所有其他的信，以确定将它放在哪。然后他又拿了一封信封，接着把所有其他的信都翻了一遍，依此类推。这种方式是不是有些眼熟呢？没错，我们在第一章的时候，分袜子就接触过这种方法；而其中那些重复的过程就是可以优化的地方。

小C在方法 1 中的方法被称为平方时间算法（Quadratic Time）。在计算中，许多对项目进行排序的最简单方法是在平方时间算法中运行的，因为就像方法 1 一样，它们都碰巧通过比较相邻项目并可能根据哪个更大哪个更小来切换它们来工作。事实上，我们可以自信地说，所有遵循这种比较相邻项目的模式的排序方法平均都在平方时间 (n2) 中运行。换句话说，如果 n 是信封的数量，我们可以通过将相邻信封比较为“以 n2 为界”来描述将这些信封放回正确顺序的函数，也就是说，通常来说，我们不可能比这更快。一些示例包括插入排序、选择排序和冒泡排序都在此限制下。

而方法2可以看出确实要比方法1更快，而其也被称为幂对数时间。

这种方式的一般方法涉及到拆分和合并，也就是说，将整个集合分解为更小的集合，并对这些变小的集合进行排序。正如我们之前说过，将集合分成两半是对数的方法，将事物重新组合在一起是线性的，因为我们会访问每个项目一次。因此，这种排序方法被称为线性排序，可以认为它比平方时间快得多，比线性时间稍慢。或者，它可能被称为对数线性或简称为 n log n——我们从拆分集合（log n）然后再将其重新组合在一起（n）所需的时间得到， n * log n。

两种著名的线性算法是由约翰·冯·诺依曼在 1945 年发明的归并排序和由托尼·霍尔在 1959 年发明的快速排序。小C的方法 2 类似于归并排序的工作原理。那里的分解步骤涉及将一组信件分成单独的组，重新组合的步骤涉及比较和组合成组的信件。在第一次完成后一步之后，我们最终会得到两组有序的组合。在第二次这样做之后，我们最终会得到一组四个有序的组，依此类推。在小C 的案例中，该过程如下图所示。