計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 卷3 排序與查找(第2版)
定 價(jià):198 元
叢書名:圖靈計(jì)算機(jī)科學(xué)叢書
- 作者:[美] 高德納(Donald E. Knuth)
- 出版時(shí)間:2017/3/1
- ISBN:9787115360656
- 出 版 社:人民郵電出版社
- 中圖法分類:TP311.1
- 頁(yè)碼:
- 紙張:膠版紙
- 版次:1
- 開(kāi)本:128開(kāi)
《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》系列被公認(rèn)為計(jì)算機(jī)科學(xué)領(lǐng)域的經(jīng)典之作,深入闡述了程序設(shè)計(jì)理論,對(duì)計(jì)算機(jī)領(lǐng)域的發(fā)展有著極為深遠(yuǎn)的影響。本書為該系列的第3卷,全面講述了排序和查找算法。書中擴(kuò)展了卷1中數(shù)據(jù)結(jié)構(gòu)的處理方法,并對(duì)各種算法的效率進(jìn)行了大量的分析。
計(jì)算機(jī)科學(xué)既壯觀又幽美,我嘗試盡自己所能,以十分恰當(dāng)?shù)姆绞絹?lái)解釋我所了解的某些片斷。很顯然,我自己并沒(méi)有任何超自然能力,但的確很喜歡講述那些似乎靜靜地等待著人們?nèi)ブv出來(lái)的故事。寫書跟講故事十分類似。
圖靈訪談之專訪Donald
E. Knuth
《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》系列著作被公認(rèn)為是對(duì)經(jīng)典計(jì)算機(jī)科學(xué)的權(quán)威論述,曾在1999年被《美國(guó)科學(xué)家》期刊評(píng)選為20世紀(jì)相當(dāng)重要的12部學(xué)術(shù)專著之一。這一宏偉浩大的工程始于1962年,計(jì)劃出版7卷,目前已經(jīng)出版了4卷。數(shù)十年來(lái),這本書一直是廣大學(xué)生、研究人員和業(yè)內(nèi)人士學(xué)習(xí)程序設(shè)計(jì)理論和實(shí)踐的無(wú)價(jià)之寶,書中各處無(wú)不體現(xiàn)著作者淵博的學(xué)識(shí)、嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度,以及深刻的洞察力。該套書自出版以來(lái),廣受眾多科學(xué)家的贊許,并對(duì)無(wú)數(shù)讀者產(chǎn)生了極其深遠(yuǎn)的影響。
《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》堪稱計(jì)算機(jī)科學(xué)領(lǐng)域的瑰寶。從事研究的人驚艷于其精美優(yōu)雅的分析,而普通程序員則一直在卓有成效地利用書中提供的各種方案解決日常問(wèn)題。這些書展現(xiàn)了作者的博觀、清晰、精確和幽默,所有的人都?xì)J佩不已。高德納是算法和程序設(shè)計(jì)領(lǐng)域的先驅(qū)者,對(duì)計(jì)算機(jī)科學(xué)發(fā)展史也有著深入的研究,書中在介紹眾多理論的同時(shí),也給出了相關(guān)的歷史和發(fā)展歷程,成為本書的一大特色。
高德納(Donald E. Knuth)知名計(jì)算機(jī)科學(xué)家,算法與程序設(shè)計(jì)技術(shù)的先驅(qū)者、斯坦福大學(xué)計(jì)算機(jī)系榮休教授、計(jì)算機(jī)排版系統(tǒng)TEX和METAFONT字體系統(tǒng)的發(fā)明人,因諸多成就以及大量富于創(chuàng)造力和具有深遠(yuǎn)影響的著作(19部書,160篇論文)而譽(yù)滿全球。近些年,他將精力全部投入到《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》七卷集的史詩(shī)般創(chuàng)作中。Knuth教授獲得過(guò)許多獎(jiǎng)項(xiàng)和榮譽(yù),包括美國(guó)計(jì)算機(jī)協(xié)會(huì)圖靈獎(jiǎng)、美國(guó)國(guó)家科學(xué)獎(jiǎng)?wù)、美?guó)數(shù)學(xué)學(xué)會(huì)的斯蒂爾獎(jiǎng),以及因發(fā)明先進(jìn)技術(shù)于1996年榮獲的京都獎(jiǎng)。1996年,設(shè)立了以其名字命名的Donald E. Knuth獎(jiǎng),授予那些為計(jì)算機(jī)科學(xué)基礎(chǔ)做出杰出貢獻(xiàn)的人。
第5 章排序. . . . . . . . . 1
*5.1 排序的組合性質(zhì). . . 8
*5.1.1 反序. . . . . . . 8
*5.1.2 多重集的排列. . . 16
*5.1.3 游程. . . . . .. . 36
5.2 內(nèi)部排序. . . . . . . 56
5.2.1 插入排序. . . . . . 61
5.2.2 交換排序. . . . . . 81
5.2.3 選擇排序. . . . . . 107
5.2.4 合并排序. . . . . . 123
5.2.5 分布排序. . . . . . 131
5.3 最優(yōu)排序. . . . . . . 140
5.3.1 比較次數(shù)最少的排序. 140
*5.3.2 比較次數(shù)最少的合并. 153
*5.3.3 比較次數(shù)最少的選擇. 161
*5.3.4 排序網(wǎng)絡(luò). . . .. . 171
5.4 外部排序. . . . . . . 194
5.4.1 多路合并和替代選擇. 197
*5.4.2 多階段合并. . . . 208
*5.4.3 級(jí)聯(lián)合并. . . . . 226
*5.4.4 反向讀取磁帶. . . 235
*5.4.5 振蕩排序. . . . . 245
*5.4.6 磁帶合并的實(shí)踐考慮. 250
*5.4.7 外部基數(shù)排序. . . . 269
*5.4.8 雙磁帶排序. . . . 273
*5.4.9 磁盤與磁鼓. . . . 279
5.5 小結(jié)、歷史與文獻(xiàn). . . 297
第6 章查找. . . . . . . . 306
6.1 順序查找. . . . . . . 308
6.2 通過(guò)鍵的比較進(jìn)行查找. .318
6.2.1 查找有序表. . . . . 318
6.2.2 二叉樹查找. . . . . 332
6.2.3 平衡樹. . . . . . . 358
6.2.4 多路樹. . . . . . . 376
6.3 數(shù)字查找. . . . . . . 385
6.4 散列. . . . . . . . . .402
6.5 輔助鍵的查找. . . . . .437