【8.7】排序算法的时间代价

一、排序算法的时间代价

• 简单排序算法的时间代价
• 排序算法的理论和实验时间
• 排序问题的下限

原因

• 一个长度为 n 的序列平均有 n(n-1)/4 对逆置
• 任何一种只对相邻记录进行比较的排 序算法的平均时间代价都是 Θ(n^2)

二、排序算法的理论和实验时间

小结

• n 很小或基本有序时插入排序比较有效
• Shell 排序选择增量以3的倍数递减
• 需要保证最后一趟增量为1
• 综合性能快速排序最佳

测试环境

• 硬件环境

• CPU:Intel P4 3G

• 内存:1G

• 软件环境

• Windows XP

• Visual C++ 6.0

随机生成待排序数组

时间测试

排序的时间测试

三、排序问题的下限

• 排序问题的时间代价在 Ω(n) (单趟扫描) 到 O(nlogn) (平均, 最差情况) 之间

• 基于比较的排序算法的 下限也为Ω(n·log n)

• 用 判定树(Decision Tree)可以说明

• 判定树中叶结点的最大深度就是排序算法在最差情况下需要的最大比较次数

• 叶结点的最小深度就是最佳情况下的最小比较次数

用判定树模拟基于比较的排序：

基于比较的排序的下限

• 对 n 个记录，共有 n! 个叶结点
• 判定树的深度至少为 log(n!)
• 在判定树深度最小的情况下最多需要 log(n!) 次比较，即 Ω(n·logn)
• 在最差情况下任何基于比较的排序算法都 至少需要 Ω(nlog n) 次比较

排序问题的时间代价

• 排序问题需要的运行时间也就是 Ω(n·log n)
• 所有排序算法都需要 O(n·log n)的运行 时间，因此可以推导出排序问题的时间代 价为 Θ (n·log n)

基数排序效率

• 时间代价为 θ(d·(n+r))(𝑟 ≪ 𝑛)，实 际上还是 θ(nlog n)
• 没有重复关键码的情况，需要 n 个 不同的编码来表示它们
• 即 d>=log_rn，在 Ω(log n)中

讨 论:

1. 本章讨论的排序算法都是基于数组实现的，可 否应用于动态链表?性能上是否有差异?
2. 试总结并证明各种排序算法的稳定性，若算法 稳定，如何修改可以使之不稳定?若算法不稳 定，可否通过修改使之稳定?
3. 试调研STL中的各种排序函数是如何组合各种 排序算法的。

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾