算法变迁史

A. 求排序算法的发展史

对于今天排序技术的探索可以追溯到19世纪，美国人口统计局的Herman Hollerith发明了第一批具有排序装置的制表机，成功地应用到1890年的美国人口普查。关于Hollerith及其制表机的故事，Leon E. Truesdell曾在【The Development of Punch Card Tabulation（Washington: U. S. Bureau of the Census, 1965）】中进行了有趣而详尽地描述。

排序例程曾经是为存储程序式计算机编写的第一个程序，因为它集中体现了计算机潜在的非数值应用。冯·诺伊曼在1954年为了检验EDVAC计算机指令代码的适用性以及评价他所建议的计算机组织的优点，编写了内部归并排序程序，Knuth在【Computing Surveys 2(1970), 247~260】中描述了这个发展细节。

在德国，K. Zuse于1945年独立编写了用于直接插入排序的程序，作为他的Plankalkul语言中线性表操作的例子之一，这一开创性的工作推迟了近30年才发表。

1946年在穆尔学校举行的有关计算的专题讨论会上，John Mauchly作了“排序和整理”的演讲，是第一个公开发表的关于计算机排序的讨论，包括直接插入排序和折半插入排序。

到1952年左右，内部排序的许多方法已在程序设计领域广为流传，但理论上的研究却相对很少。Daniel Goldenberg用Whirlwind计算机编写了5个不同方法的排序程序，分别就最好情况和最坏情况进行了分析。

由Howard B. Demuth于1956年撰写的博士论文【Electronic Data Sorting. Stanford University, 1956】可以说是一篇非常值得关注的论文，因为这篇论文有助于奠定计算复杂性理论的基础。论文利用循环的、线性的以及随机的存储器，考虑了排序问题的3个抽象模型，并对每个模型提出了最优（或接近最优）的方法。Demuth的论文建立了如何把理论同实践相联系的重要思想。

事实上，计算的大多数早期历史都出现在比较难以得到的报告中，因为那时仅有少数人同计算机打交道。有关排序文献的第一次付印是在1955年，用的是三篇重要的综述性文章。第一篇文章是由J. C. Hosken撰写的【Proc. Eastern Joint Computer Conference 8(1955), 39~55】，综述了在计算机上进行排序的方法，以及所有可利用的专用设备，文中的54项参考文献大多数是以厂家的手册为基础的。第二篇文章是由E. H. Friend撰写的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956), 134~168】是排序技术发展史的一个重要里程碑，Friend对相当多的内部和外部排序算法给出了细致的描述。第三篇文章是由D. W. Davies撰写的【Proc. Inst. Elec. Engineers 103B, Supplement 1(1956), 87~93】。

1962年11月ACM主持召开了一次关于排序的研讨会，在会上宣读的大多数论文都发表在COMMUNICATIONS OF THE ACM1963年5月的刊物上，这些论文是当时技术发展水平的很好代表。