計算器程序設計藝術(卷3):排序與查找(第2版) | 美妙體態瑜珈在你家 - 2024年10月
計算器程序設計藝術(卷3):排序與查找(第2版)
《電腦程式設計藝術》系列被公認為電腦科學領域的經典之作,深入闡述了程式設計理論,對電腦領域的發展有著極為深遠的影響。
本書為該系列的第3卷,全面講述了排序和查找演算法。書中擴展了卷1中資料結構的處理方法,並對各種演算法的效率進行了大量的分析。
高德納(Donald E. Knuth)知名計算機科學家,算法與程序設計技術的先驅者、斯坦福大學計算機系榮休教授、計算機排版系統TEX和METAFONT字體系統的發明人,因諸多成就以及大量富於創造力和具有深遠影響的著作(19部書,160篇論文)而譽滿全球。近些年,他將精力全部投入到《計算機程序設計藝術》七卷集的史詩般創作中。Knuth教授獲得過許多獎項和榮譽,包括美國計算機協會圖靈獎、美國國家科學獎章、美國數學學會的斯蒂爾獎,以及因發明先進技術於1996年榮獲的京都獎。1996年,設立了以其名字命名的Donald E. Knuth獎,授予那些為計算機科學基礎做出傑出貢獻的人。
第5章 排序. . . . . . . . . 1
5.1 排序的組合性質. . . 8
5.1.1 反序. . . . . . . 8
5.1.2 多重集的排列. . . 16
5.1.3 游程. . . . . .. . 36
5.2 內部排序. . . . . . . 56
5.2.1 插入排序. . . . . . 61
5.2.2 交換排序. . . . . . 81
5.2.3 選擇排序. . . . . . 107
5.2.4 合併排序. . . . . . 123
5.2.5 分佈排序. . . . . . 131
5.3 最優排序. . . . . . . 140
5.3.1 比較次數最少的排序. 140
5.3.2 比較次數最少的合併. 153
5.3.3 比較次數最少的選擇. 161
5.3.4 排序網路. . . .. . 171
5.4 外部排序. . . . . . . 194
5.4.1 多路合併和替代選擇. 197
5.4.2 多階段合併. . . . 208
5.4.3 級聯合並. . . . . 226
5.4.4 反向讀取磁帶. . . 235
5.4.5 振盪排序. . . . . 245
5.4.6 磁帶合併的實踐考慮. 250
5.4.7 外部基數排序. . . . 269
5.4.8 雙磁帶排序. . . . 273
5.4.9 磁片與磁鼓. . . . 279
5.5 小結、歷史與文獻. . . 297
第6章 查找. . . . . . . . 306
6.1 順序查找. . . . . . . 308
6.2 通過鍵的比較進行查找. .318
6.2.1 查找有序表. . . . . 318
6.2.2 二叉樹查找. . . . . 332
6.2.3 平衡樹. . . . . . . 358
6.2.4 多路樹. . . . . . . 376
6.3 數字查找. . . . . . . 385
6.4 散列. . . . . . . . . .402
6.5 輔助鍵的查找. . . . . .437