計算機程序設計藝術（第3卷 英文版·第2版）

前言

本書是第1卷的第2章中有關信息結構內容的自然延續(xù)，因為它為其他基本結構化思想增加了線性有序數(shù)據(jù)的概念。書名中的“排序與查找”可能會使人誤以為本書面向的只是從事一般性排序工作或信息檢索工作的系統(tǒng)程序員。事實上，排序與查找為討論眾多重要的一般性問題提供了一個理想的框架：·好算法是怎么發(fā)現(xiàn)的？·如何改進給定的算法和程序？·如何從數(shù)學的角度分析算法的效率？·對于給定的任務，如何在不同的算法之間做出合理的選擇？·在什么意義下，可以證明算法是“最可行的”？·計算理論同實際考慮如何相互影響？·如何將磁帶、磁鼓或磁盤這樣的外存有效應用于大型數(shù)據(jù)庫？事實上，我認為程序設計的幾乎所有重要的方面都與排序或查找有關！本卷包含整套書中的第5章和第6章。第5章討論排序，這個大問題主要劃分成兩個部分，即內部排序和外部排序。此外，這一章還有幾個輔助性小節(jié)，討論了有關排列（5.1節(jié)）和最優(yōu)排序方法（5.3節(jié)）的輔助理論。第6章討論在表或文件中查找特定項的問題，該問題可以分為順序查找、通過比較鍵進行查找、按數(shù)位性質進行查找以及散列法查找等，然后討論了更難的輔鍵查找問題。這兩章內容有著驚人的相互影響和很強的相似性。除了第2章介紹的信息結構外，本書還討論了兩種重要的信息結構，即優(yōu)先隊列（5.2.3節(jié)）和表示成平衡樹的線性表（6.2.3節(jié)）。與第l卷和第2卷一樣，本書包含了其他出版物所沒有的許多內容。許多人曾經以書面或口頭的形式向我表達了他們的思想，我希望在用自己的語言表述時沒有過度地歪曲他們的原意。

內容概要

《計算機程序設計藝術》系列被公認為計算機科學領域的權威之作，深入闡述了程序設計理論，對計算機領域的發(fā)展有著極為深遠的影響。本書是該系列的第3 卷，擴展了第1 卷中信息結構的內容，主要講排序和查找。書中對排序和查找算法進行了詳細的介紹，并對各種算法的效率做了大量的分析?！　”緯m合從事計算機科學、計算數(shù)學等各方面工作的人員閱讀，也適合高等院校相關專業(yè)的師生作為教學參考書，對于想深入理解計算機算法的讀者，是一份必不可少的珍品。

作者簡介

　Donald E.Knuth 
　　算法和程序設計技術的先驅者，是計算機排版系統(tǒng)TEX和METAFONT的發(fā)明者。 Donald.E.Knuth(唐納德.E.克努特，中文名高德納)是斯坦福大學計算機程序設計藝術的榮譽退休教授，Knuth教授獲得了許多獎項和榮譽，包括美國計算機協(xié)會圖靈獎(ACM Turing Award)

書籍目錄

chapter 5 sorting 　*5.1. combinatorial properties of permutations 　*5.1.1. inversions　　　　*5.1.2. permutations of a multiset　　　*5.1.3. runs　　　*5.1.4. tableaux and involutions　  　5.2. internal sorting　　　　　5.2.1. sorting by insertion　　　　5.2.2. sorting by exchanging　　　　　5.2.3. sorting by selection　　　5.2.4. sorting by merging　　　　5.2.5. sorting by distribution　　5.3. optimum sorting 　5.3.1. minimum-comparison sorting　  　*5.3.2. minimum-comparison merging　  　*5.3.3. minimum-comparison selection　　*5.3.4. networks for sorting　　　5.4. external sorting　　　　5.4.1. multiway merging and replacement selection　  　*5.4.2. the polyphase merge　　　　　*5.4.3. the cascade merge　　*5.4.4. reading tape backwards　  　*5.4.5. the oscillating sort 　  　*5.4.6. practical considerations for tape merging　　*5.4.7. external radix sorting　　　　　*5.4.8. two-tape sorting　　　*5.4.9. disks and drums　5.5. summary, history, and bibliography　  chapter 6 searching　　　6.1. sequential searching 　  　6.2. searching by comparison of keys　  　6.2.1. searching an ordered table　  　6.2.2. binary tree searching　  　6.2.3. balanced trees　　  　6.2.4. multiway trees 　　　6.3. digital searching 　6.4. hashing　　　6.5. retrieval on secondary keys　　　　answers to exercises 　appendix a tables of numerical quantities 　1. fundamental constants (decimal)　  　2. fundamental constants (octal)　  　3. harmonic numbers, bernoulli numbers, fibonacci numbers appendix b index to notations　 index and glossary

章節(jié)摘錄

插圖：

媒體關注與評論

這一多卷本的鴻篇巨著被公認為是對經典計算機科學的權威論述，數(shù)十年來，前3卷一直是廣大學生、研究人員和業(yè)內人士學習程序設計理論和實踐的無價之寶。這是一部包含一切基礎算法的寶典，是它教給了這一代軟件開發(fā)人員關于計算機程序設計的絕大多數(shù)知識?！　　狟yte雜志1995年9月刊無數(shù)的讀者談到過Knuth的著作對于自己的深刻影響。從事研究的人驚訝于他精美優(yōu)雅的分析，而普通程序員則一直在卓有成效地利用書中提供的各種方案解決日常問題。這些書展現(xiàn)了作者的博觀、清晰、精確和幽默，所有的人都欽佩不已。我簡直說不清楚這些書給我的學習和娛樂帶來了多少歡樂時光。我在各種場合一有空就仔細研讀，在車上，在餐館，上班時，回到家里……甚至有次觀看我兒子的球賽，趁他沒上場的時候，我還拿出來看了一陣子?！　　狢harles Long它本來是當參考書寫的，但有些人卻發(fā)現(xiàn)每一卷都可以興致勃勃地從頭讀到尾。有位中國的程序員甚至把它比做讀詩。如果你自以為是一個很好的程序員，請去讀讀Knuth的《計算機程序設計藝術》吧……要是你真把它讀下來了，就毫無疑問可以給我遞簡歷了。　　——比爾·蓋茨不管你的背景如何，只要你想認真地編寫計算機程序。都有很好的理由把這套書的每一卷抱回家。便于研究和工作時隨時翻閱。20年來Knuth第一次全部修訂了這3卷。我發(fā)現(xiàn)，只要翻一翻這些書，就會立竿見影地“鎮(zhèn)住”計算機?！　　狫onathan Laventhol

編輯推薦

《計算機程序設計藝術 卷3:排序與查找(英文版·第2版)》：《計算機程序設計藝術》系列著作對計算機領域產生了深遠的影響。這一系列堪稱一項浩大的工程，自1962年開始編寫，計劃出版7卷，目前已經出版了4卷?！睹绹茖W家》雜志曾將這套書與愛因斯坦的《相對論》等書并列稱為20世紀最重要的12本物理學著作。目前Knuth正將畢生精力投入到這部史詩性著作的撰寫中。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機程序設計藝術（第3卷 英文版·第2版） PDF格式下載

---