8.6.1 内部排序算法的比较

教材导航 · 第8章

原书定位

印刷页P380起,对应PDF第392页。下文为目视整理的知识提要;完整内容见原书对照。

算法平均时间最坏时间常见辅助空间稳定性
直接插入O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)稳定
折半插入O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)稳定
冒泡O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)稳定
简单选择O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)不稳定
希尔依增量序列依增量序列O(1)O(1)不稳定
快速O(nlog⁡n)O(n\log n)O(n2)O(n^2)平均 O(log⁡n)O(\log n)、最坏 O(n)O(n)不稳定
堆O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(1)O(1)不稳定
归并O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)数组实现 O(n)O(n)稳定
LSD 基数O(d(n+r))O(d(n+r))O(d(n+r))O(d(n+r))链式 O(r)O(r);数组常为 O(n+r)O(n+r)稳定
计数O(n+k)O(n+k)O(n+k)O(n+k)含输出缓冲 O(n+k)O(n+k)稳定实现可行

简单选择的记录比较次数固定;归并的比较次数数量级稳定,但具体值会变;折半插入的比较次数也会因查找路径略有差别,不能仅由 O(nlog⁡n)O(n\log n) 推出任意输入比较总数完全相同。

各种排序算法性能对照

各种排序算法性能对照,原书P381。

对应练习

8.6 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P380,PDF第392页

原书对照,原书P381,PDF第393页