計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第3卷 英文版·第2版）

前言

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

內(nèi)容概要

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

作者簡介

　Donald E.Knuth 
　　算法和程序設(shè)計(jì)技術(shù)的先驅(qū)者，是計(jì)算機(jī)排版系統(tǒng)TEX和METAFONT的發(fā)明者。 Donald.E.Knuth(唐納德.E.克努特，中文名高德納)是斯坦福大學(xué)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)的榮譽(yù)退休教授，Knuth教授獲得了許多獎項(xiàng)和榮譽(yù)，包括美國計(jì)算機(jī)協(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é)摘錄

插圖：

媒體關(guān)注與評論

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第3卷 英文版·第2版） PDF格式下載

---