你相信吗，排序算法难倒过计算机科学家丹尼尔.希利斯（W.DanielHillis）

丹尼尔.希利斯（W.Daniel Hillis）（born September 25 ， 1956) ,当今著名的计算机科学家，参与世界上速度最快的计算机设计工作，在美国拥有三四十项专利，他是思考机器公司的首席科学家与创办人之一，并是主要产品：“连接机器”并行超级计算机的首要设计者。
相传，他还是麻省理工学院的一名本科生的时候，在宿舍里被舍友的袜子惊呆了。大多数学生刚刚踏进宿舍的时候，关心的可能会是舍友是不是爱干净，彼此的生活习惯会不会契合等等问题，而希利斯则不然。
【你相信吗，排序算法难倒过计算机科学家】他的室友从干净的洗衣篮中拿出一只袜子，接着又随机拿出另一只袜子，如果两只袜子不配对，就把第二只放回去重新再拿一次，一直重复这个过程，直到袜子配对成功。
文章插图
想象一下，假如洗衣篮中共有10双不同的袜子，按照这种拿法，配好第一对袜子最多需要取19次。配好第二对最多需要17次，同理，如果把全部10双袜子全部配好对，最多需要110次拿袜子。
（PS:如果不知道为啥是这么多次，可以私信小编，改天我们专门来说一说排列组合问题）
惊呆了的希利斯，提出了换宿舍……
文章插图
同样是这个袜子问题，就连传奇式密码学家、计算机科学家、图灵奖得主罗恩.李维斯特被问到的时候，也坦诚的笑着说“我被袜子打败了。 ”
当时，他光脚穿着凉鞋……
文章插图
排序是计算机的核心内容。不夸张的说，没有排序，计算机就不会变成现实。
1880年的一天，美国人口普查局的办公室里，一名叫赫尔曼·霍尔瑞斯的20岁年轻人正盯着那堆小山般的人口登记册发呆。那里面记录着前不久数以万计的普查员费尽千辛万苦采集回来的人口数据，而要用效率低下的手摇计算器把这些数据分析完毕，至少要花费7年时间。这意味着几乎要到下一次人口普查时，美国民众才能得知这次人口普查的结果。
甚至据他估算， 1890年美国人口总数将在5000万的基础上增加1200万。如果还用老一套的办法统计，至少需要10年时间才能把所有数据全部搞定。
严峻的现实让霍尔瑞斯下定决心：必须进行改革，要发明一种能高效完成繁重统计制表工作的机器！
霍尔瑞斯从当时使用的打孔火车票那里找到了灵感，发明了一种可以存储信息的打孔统计卡用来完成排序工作：在相同规格的硬纸卡片上设立要普查的各个项目，如性别、年龄、籍贯等等，然后根据调查结果在相应项目的位置上打孔，比如：约翰是一名40岁的男性公民，那么就在“性别”栏目“男”的名下打个小孔；“年龄”栏目的“40”之下也打个小孔，如此类推，一张打孔的卡片上就记录了一名公民详细的个人信息。然后再发明一种机器，把这些信息“读”出并统计。
文章插图
1889年，霍尔瑞斯获得专利，美国1890奶奶的人口普查中就采用了霍尔瑞斯发明的“霍尔瑞斯计算机” 。
1911年，霍尔瑞斯自己的公司与另外几家公司合并，变成了计算——制表——记录公司，之后，公司改名为国际商用机器公司，即IBM 。
从计算机诞生直到20世纪，排序一直是推动计算机发展的一大动力。为“存储程序”计算机编写的第一个代码就是一个排序程序。
20世纪60年代，据评估，世界上超过1/4的计算资源用于排序工作。无论是查找最大值或者最小值，最常见数据或者最罕见数据，还是索引、标记副本、或者根据要求进行查找，其核心工作都是排序。
在我们的日常生活中，排序也时时在给为我们提供着便利。比如，你在收邮件的时候，你通常看到的是按照接收邮件的时间顺序排列而成的未读邮件的列表。
文章插图
再比如，你在大众点评APP上搜索附近的美食的时候， APP反馈给你的结果，是将成百上千的商家根据地理位置的远近程度，以及到过的客户的评价指数，综合给出的排序。
文章插图