計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 卷3 排序與查找(第2版)
定 價(jià):198 元
叢書(shū)名:圖靈計(jì)算機(jī)科學(xué)叢書(shū)
- 作者:[美] 高德納(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)的影響。本書(shū)為該系列的第3卷,全面講述了排序和查找算法。書(shū)中擴(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)的故事。寫(xiě)書(shū)跟講故事十分類似。
圖靈訪談之專訪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),這本書(shū)一直是廣大學(xué)生、研究人員和業(yè)內(nèi)人士學(xué)習(xí)程序設(shè)計(jì)理論和實(shí)踐的無(wú)價(jià)之寶,書(shū)中各處無(wú)不體現(xiàn)著作者淵博的學(xué)識(shí)、嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度,以及深刻的洞察力。該套書(shū)自出版以來(lái),廣受眾多科學(xué)家的贊許,并對(duì)無(wú)數(shù)讀者產(chǎn)生了極其深遠(yuǎn)的影響。
《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》堪稱計(jì)算機(jī)科學(xué)領(lǐng)域的瑰寶。從事研究的人驚艷于其精美優(yōu)雅的分析,而普通程序員則一直在卓有成效地利用書(shū)中提供的各種方案解決日常問(wèn)題。這些書(shū)展現(xiàn)了作者的博觀、清晰、精確和幽默,所有的人都?xì)J佩不已。高德納是算法和程序設(shè)計(jì)領(lǐng)域的先驅(qū)者,對(duì)計(jì)算機(jī)科學(xué)發(fā)展史也有著深入的研究,書(shū)中在介紹眾多理論的同時(shí),也給出了相關(guān)的歷史和發(fā)展歷程,成為本書(shū)的一大特色。
高德納(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部書(shū),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 磁盤(pán)與磁鼓. . . . 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 二叉樹(shù)查找. . . . . 332
6.2.3 平衡樹(shù). . . . . . . 358
6.2.4 多路樹(shù). . . . . . . 376
6.3 數(shù)字查找. . . . . . . 385
6.4 散列. . . . . . . . . .402
6.5 輔助鍵的查找. . . . . .437