1700495068
1700495069
从某种非常重要的意义上看，合并排序算法给出的O（nlogn）线性对数时间肯定是我们可以得到的最佳效果。已经有人证明，如果通过一系列面对面直接比较的方法对n个事物进行完全排序，比较的次数不可能少于O（nlogn）。这是一条普世法则，是不可能违背的。
1700495070
1700495071
但是，严格说来，这条法则并不能平息排序问题上的所有争议。有的时候我们并不需要完全排序，有的时候根本不需要逐项比较也能完成排序工作。正是因为有这两个原因，实践中的粗略排序速度也可以比线性对数时间快。桶排序算法非常漂亮地展现了这个特点，而普雷斯顿分类排序中心就是桶排序的一个完美实例。
1700495072
1700495073
在桶排序中，排序对象按照排序类别分成若干组，类别之间更精细的排序问题会被留到后面解决，在分组时不予考虑。（在计算机科学中，“桶”这个术语仅表示一组未排序的数据，但是，金县图书馆系统等现实世界中最有影响力的桶排序用户则把这个表达按照字面含义来理解。）对于这一步骤，有人提出反对意见：如果你希望将n个对象分装到m个桶中，分组工作需要的时间是O（mn），也就是说，时间一定与对象数量和桶数量的乘积成比例关系。但是，只要桶的数量与排序对象的数量相比显得比较小，大O符号就认为这个时间约等于O（n），即线性时间。
1700495074
1700495075
真正打破线性对数壁垒的关键，是了解排序对象的分布情况。如果桶选得不合适，排序的效果就不会太好。例如，如果所有的书都被投放到同一个箱子里，排序工作就没有任何进展。但是，如果桶选得非常合适，所有项目都被分到大小差不多的组里，就表明已经朝着完全有序前进了一大步（鉴于排序工作在本质上遵循“规模越大，难度越大”这条准则）。普雷斯顿分类排序中心的任务是按照目的地，而不是字母顺序，进行排序，因此在选桶的时候考虑的是流通统计数据。有的分支流通量比较大，因此他们就分配给这些分支两只箱子，有时甚至是三只箱子。
1700495076
1700495077
人在完成排序工作时，如果对排序对象有类似的了解，也会对他们有利。为了现场观看专家的排序工作，我们前往加州大学伯克利分校的主图书馆和墨菲特图书馆，进行了一次实地考察。这些图书馆的书架长度加起来至少有52英里，所有的书都靠人工整理。归还到图书馆的书首先被放到后台，然后根据美国国会图书馆藏书书目，重新放回到不同的书架上。例如，一组书架上放有一堆最近归还的书籍，藏书书目都在PS3000到PS9999之间。然后，学生助手将这些图书装到小车上，每车装150本，所有的书都以适当的顺序放置，以方便他们放回到图书馆的书架上。学生们都接受过一些基本的排序训练，但是一段时间之后，他们都会找到一些适合自己的办法。积累了一定经验之后，他们可以在不到40秒的时间里，就把小车上150本书全部排好次序。这些经验的主要作用是让他们预先知道这些书有哪些特点。
1700495078
1700495079
伯克利分校化学专业的学生乔丹·何是一位图书分类排序高手。他一边整理着PS3000-PS9999书架上的一大堆图书，一边告诉我们：
1700495080
1700495081
据我的经验，书目号在3500至3600之间的书很多，因此我首先找3500以下的书，先粗排，再细排。等3500以下的书都排好之后，我知道3500以上的书（也就是3500至3599这些书）是个大头，所以我想把这些书单独排好序。如果这些书的数量太多，我可能会进一步细分，分成3510-3519、3520-3529、3530-3539等。
1700495082
1700495083
乔丹总是把25本左右的书编成一组，全部排好序之后，装到小车上。排序的时候，他使用的确实是插入排序法。他精心想出来的办法是一种桶排序法。他事先就知道各种书目号对应的图书数量，因此他清楚应该如何选桶。结果，这个办法取得了非常好的效果。
1700495084
1700495085
1700495086
1700495087
1700495089
算法之美：指导工作与生活的算法 排序是搜索的准备工作
1700495090
1700495091
掌握了这些排序算法，你下一次整理书架时就应该能派上用场。同奥巴马一样，你也会知道不能使用冒泡排序法。好的办法（得到图书馆工作人员和机器的共同认证）是使用桶排序，等到将排序对象分成足够小的组之后，再使用插入排序，或者干脆举办比萨派对，使用合并排序。
1700495092
1700495093
但是，如果你邀请计算机科学家帮助你完成这项工作，他们询问的第一个问题应该是：你到底为什么要整理这些图书？
1700495094
1700495095
老师经常告诉那些本科生，计算机科学研究的就是如何取舍的问题。在前面讲到观察与行动以及探索与利用之间的矛盾时，就已经讨论过这个观点。而排序与搜索之间的取舍是最重要的取舍问题之一，其基本原理是：人们投入精力为物品排序是一种先发制人的措施，目的是保证以后无须在搜索上投入精力。平衡点应该如何确定，取决于当时情况的具体参数，但是，如果认为排序的价值仅仅是为未来的搜索提供支持，那么你会有一个令人吃惊的发现：
1700495096
1700495097
混乱无序也无伤大雅！
1700495098
1700495099
如果你从来不在某些物品中搜索某个目标，那么为这些物品排序就纯粹是一种浪费。如果你从来不为某些物品排序，那么你在其中搜索的效率就会很低。
1700495100
1700495101
因此，摆在我们面前的问题已经变成如何提前预估未来的用途。
1700495102
1700495103
谷歌等互联网搜索引擎是排序带来的一个典型益处。很难想象，谷歌可以利用你输入的搜索词，在不到半秒的时间内搜索整个互联网。事实上，谷歌做不到，不过它也无须这样做。如果你是谷歌，你几乎可以肯定以下3点：（1）你的数据会被搜索；（2）它不仅会被搜索，而且会被多次搜索；（3）与搜索所需时间相比，排序所需时间“价值较低”。（这里，排序是由机器提前完成的，排序结果暂时无用；搜索是由用户完成的，而用户的时间非常宝贵。）所有这些因素都倾向于预先排序，而谷歌和其他搜索引擎也正是这样做的。
1700495104
1700495105
因此，你是否应该整理你的书架呢？大多数家庭并不具备支持整理书架的任何条件。我们几乎不会在书架上的藏书中搜索某个书名，因此无序搜索的成本非常低：任何一本书，只要我们知道它的大致位置，就可以快速地找到它。在井然有序的书架上找到一本书或许需要2秒钟，而在一个胡乱堆放的书架上找到一本书则可能需要10秒钟，但是两者之间并不存在难以接受的差距。我们因为迫切需要某本书，而宁愿预先花几个小时时间书架，为将来再找它省下几秒钟，这种情况几乎不会发生。此外，我们的双眼可以快速搜索，而双手排序的速度却非常慢。
1700495106
1700495107
结论很明确：整理书架与在书架上浏览一遍相比，前者需要更多的时间和精力。
1700495108
1700495109
你可能不会每天都关注乱七八糟的书架，但是电子邮件的收件箱绝对是搜索轻松击败排序的另一个舞台。人工将电子信息归档到文件夹中所花费的时间与在现实世界中纸质文件归档所需的时间差不多，但是电子邮件的搜索速度要比纸质邮件高得多。随着搜索成本的下降，排序的价值也会随之降低。
1700495110
1700495111
IBM的研究科学家、加州大学圣克鲁兹分校教授史蒂夫·惠特克是研究人们处理电子邮件方式的知名专家之一。近20年来，惠特克一直在研究人们是如何管理个人信息的。（1996年，他写了一篇关于“电子邮件过载”的论文，当时很多人甚至还没有电子邮箱。）2011年，惠特克领导了一项关于电子邮件用户搜索和排序习惯的研究，其研究结果发表在一篇名为“我整理电子邮件是一种浪费时间的行为吗？”的文章中。我在这里来个剧透吧：结论不仅是肯定，而且是非常肯定。惠塔克指出：“这是一种经验，同时也是一种体验。在采访中谈论这些邮件整理问题时，他们告诉我，他们通常会讨论这个问题，并且认为这件事浪费了他们大量时间。”
1700495112
1700495113
计算机科学表明，混乱的危害和秩序的危害是可以量化的，他们的成本都可以用时间这个“货币”来衡量。杂乱无序可能会被认为是一种拖延的行为——把责任推给未来的自己，而且还要连本带息偿还我们不愿意提前支付的债务。但是，详细情况还要更加微妙。有时，混乱不仅仅是轻松的选择，还是一个最优选择。
1700495114
1700495115
1700495116
1700495117
[
上一页 ]
[ :1.700495068e+09 ]
[
下一页 ]