計算器程序設計藝術（卷3）：排序與查找（第2版）

第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