演算法變遷史

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月的刊物上，這些論文是當時技術發展水平的很好代表。