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

前言

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

內(nèi)容概要

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

作者簡(jiǎn)介

　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教授獲得了許多獎(jiǎng)項(xiàng)和榮譽(yù)，包括美國(guó)計(jì)算機(jī)協(xié)會(huì)圖靈獎(jiǎng)(ACM Turing Award)

書(shū)籍目錄

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)注與評(píng)論

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---