1700494909
算法之美：指导工作与生活的算法 03 排序 建立秩序
1700494910
1700494911
罗伯特·考德雷，《词汇表》
1700494912
1700494913
如果你要查的单词的首字母是a，就在《词汇表》开头部分查找。如果首字母是v，就到靠后的位置查找。此外，如果开头的两个字母是ca，就在字母c项下的开头部分查找。如果是cu，则应到字母c部分的末尾处查找。以此类推。
1700494914
1700494915
多年以前，丹尼·希利斯是麻省理工学院的一名本科生。当时他还没有创立“思维机器公司”，也还没有发明著名的“连接机器”并行超级计算机，而是住在学生宿舍里，目瞪口呆地看着室友的袜子。
1700494916
1700494917
与许多大学生不同的是，希利斯关心的并不是室友的卫生状况。让他感到吃惊的，并不是他勤于洗袜子，室友却从来不洗，而是接下来发生的事情。
1700494918
1700494919
室友从干净的洗衣篮中拿出一只袜子。接着，又随机抽出另一只袜子。如果两只袜子不配对，他就把第二只扔回去。然后继续这个过程，他把袜子一个一个地抽出来，然后把它们扔回去，直到为第一只袜子成功配对为止。
1700494920
1700494921
洗衣篮里一共有10双不同的袜子。按照这个方法，配好第一对最多需要取19次，配好第二对又可能需要17次。如果要把20只袜子全部配成对，这个室友可能需要从洗衣篮里取110次袜子。
1700494922
1700494923
任何未来的计算机科学家看到这幅情景，可能都会要求换宿舍。
1700494924
1700494925
应该如何对袜子进行排序的问题引起了计算机科学家的热议。2013年，有人在“栈溢出”编程网站上贴出了一个关于袜子的问题，立刻引发了长达12000个单词的争论。
1700494926
1700494927
当我们对传奇式密码学家、计算机科学家、图灵奖得主罗恩·李维斯特提起这个话题时，他向我们坦承：“我被袜子打败了！”
1700494928
1700494929
当时，他穿着凉鞋。
1700494930
1700494931
1700494932
1700494933
1700494935
算法之美：指导工作与生活的算法 排序狂潮
1700494936
1700494937
排序是计算机的核心内容。事实上，从很多方面看，如果没有排序，计算机就不会变成现实。
1700494938
1700494939
19世纪末期，美国人口每10年就会增加30%。1870年，美国人口普查只有5个“调查科目”，到1880年，就增加到了200多个。1880年人口普查的制表工作花了8年，在1890年人口普查即将开始时才勉强完工。当时，有一位作家评论说：“调查人员整天埋头整理那些令人头皮发麻的统计数字，竟然没有失明，也没有发疯，这真是一大奇迹。”所有从事人口普查的工作人员都不堪重负，濒临崩溃。这个局面已经到了不得不改变的地步。
1700494940
1700494941
发明家赫尔曼·霍尔瑞斯从当时使用的打孔火车票那里找到灵感，发明了一种可以存储信息的打孔统计卡和一种机器，用来完成计数与排序工作。他把这套系统称作“霍尔瑞斯计算机”。1889年，霍尔瑞斯获得专利，美国政府在1890年的人口普查中采用了霍尔瑞斯计算机。在这之前，从来没有人看到过这样的机器。一位惊叹不已的旁观者说：“这个装置就像众神的磨坊一样准确无误，速度则完胜对方。”然而，另一个人认为这项发明的用途十分有限：“除了政府以外，没有人愿意使用它，因此发明者不可能发财。”霍尔瑞斯把这个预言制成剪报并保存了下来，但是事实证明，这个预言并不完全正确。1911年，霍尔瑞斯公司与另外几家公司合并，变成了计算-制表-记录公司。几年之后，公司改名为国际商用机器公司，即IBM。
1700494942
1700494943
从计算机诞生直到进入20世纪，排序一直是推动计算机发展的一大动力。为“存储程序”计算机编写的第一个代码是一个高效排序程序。事实上，正是因为计算机的能力超越了IBM的专用卡片分类机，所以美国政府相信它们在通用机器上投入巨额资金的决定是正确的。到20世纪60年代，一项研究估计，世界上超过1/4的计算资源被用于排序。难怪排序对于处理几乎任何类型的信息来说都是至关重要的。无论是查找最大值或最小值，最常见数据或最罕见数据，还是清点、索引、标记副本，或者根据你的要求进行查找，其核心工作通常都是排序。
1700494944
1700494945
但是，排序不仅用于这些方面。毕竟，排序的主要原因之一是将内容变成方便人眼观察的形式，这意味着排序也是人类信息体验的关键。排序列表无处不在。就像鱼儿问“水是什么”一样，我们只有有意识地去感知，才会发现排序无处不在。
1700494946
1700494947
即使电子邮件收件箱有数千封邮件，它也通常会根据收件时间显示排在前面的50封。利用点评网站Yelp寻找餐厅时，它也会将成百上千家餐厅根据邻近程度与用户评分排序，然后为你显示前十几名。博客按日期对博文进行排序，显示一个不是很长的博文清单。脸书的动态信息、推特的信息流和红迪网的主页都是根据某些属性对内容进行排序，然后以列表的形式显示出来。我们把谷歌和必应等网站称作“搜索引擎”，但是这个称呼并不是非常恰当，因为它们其实都是排序引擎。作为接收全球信息的一种手段，谷歌占有非常明显的优势，究其原因，与其说是它可以在成千上万的网页中找到我们需要的文本（20世纪90年代，谷歌的竞争对手同样可以出色地完成这个任务），不如说是因为谷歌可以将这些网页进行有效地排序，然后只把关系最密切的前10个网页显示出来。
1700494948
1700494949
从很多方面看，在庞大排序表的顶部截取一部分，就可以当作通用的用户界面。
1700494950
1700494951
计算机科学可以帮助我们了解所有上述情况的深层次内容。当我们被账单、文件、书本、袜子等团团包围，希望厘出头绪（这种情况每天都会发生，而且比我们想象的还要多）时，这些知识又可以转化为一种深刻认识，帮助我们解决难题。通过量化混乱状况的缺点（和优点），计算机科学还告诉我们，在一些情况下，我们其实根本不应该排出次序。
1700494952
1700494953
此外，当我们开始看排序结果时，我们知道被排序的不仅是信息——被我们排序的其实是人！建立先后次序的计算机科学最适合大展身手的舞台可能是运动场和拳击场，因此，学会排序有助于理解人类可以和谐相处、偶尔才会拳脚相向的原因。也就是说，排序可以为我们提供一些令人吃惊的线索，帮助我们了解社会的本质。所谓社会，就是我们维持的另外一种更重要、规模更大的秩序。
1700494954
1700494955
1700494956
1700494957
[
上一页 ]
[ :1.700494908e+09 ]
[
下一页 ]