8.6.1 内部排序算法的比较
原书定位
印刷页P380起,对应PDF第392页。下文为目视整理的知识提要;完整内容见原书对照。
| 算法 | 平均时间 | 最坏时间 | 常见辅助空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | 稳定 | |||
| 折半插入 | 稳定 | |||
| 冒泡 | 稳定 | |||
| 简单选择 | 不稳定 | |||
| 希尔 | 依增量序列 | 依增量序列 | 不稳定 | |
| 快速 | 平均 、最坏 | 不稳定 | ||
| 堆 | 不稳定 | |||
| 归并 | 数组实现 | 稳定 | ||
| LSD 基数 | 链式 ;数组常为 | 稳定 | ||
| 计数 | 含输出缓冲 | 稳定实现可行 |
简单选择的记录比较次数固定;归并的比较次数数量级稳定,但具体值会变;折半插入的比较次数也会因查找路径略有差别,不能仅由 推出任意输入比较总数完全相同。

各种排序算法性能对照,原书P381。
对应练习
关联知识
原书对照
展开原书对照截图

