電腦程式設計藝術卷3：排序與查找（第2版）

內容簡介

《電腦程式設計藝術》系列被公認為計算機科學領域的經典之作，深入闡述了程式設計理論，對計算機領域的發展有著極為深遠的影響。本書為該系列的第3卷，全面講述了排序和查找算法。書中擴展了卷1中數據結構的處理方法，並對各種算法的效率進行了大量的分析。

第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