排序问题的时间代价 基数排序效率 ■在最差情况下任何基于比较的排序算法 ■时间代价为e(dn),实际上还是 都需要p( nlog n)次比较,因此最差情 况时间代价就是Q( n log n) e(nlog n 那么排序问题本身需要的运行时间也就 没有重复关键码的情况,需要n个不 是9(n·logm) 同的编码来表示它们 所有排序算法都需要e( n log n)的运行 时间,因此可以推导出排序问题的时间 也就是说,d=logn,即在Qogn中 代价为e( n log n) 北大脑张铭输写 真大物单张写 小结 ■71基本概念 75堆排序 n排序码、正逆序、稳定性 选择排序 ■72三种O(n2)的简单排序 76分配排序和基数排序 比较次数、移动次数(交换vs移动) 链表、地址排序 ■73She|排序 77排序算法的理论和实验时间代价 ■74基于分治法的排序 判定树 n快速排序、归并排序 京大管息张铭编写 莉命究 北真大张写 ENDI 2828 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 163 排序问题的时间代价 „ 在最差情况下任何基于比较的排序算法 都需要Ω(nlog n)次比较，因此最差情 况时间代价就是Ω(n· log n) „ 那么排序问题本身需要的运行时间也就 是Ω(n· log n) „ 所有排序算法都需要Θ(n· log n)的运行 时间，因此可以推导出排序问题的时间 代价为 Θ (n· log n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 164 基数排序效率 „ 时间代价为Θ(d·n)，实际上还是 Θ(nlog n) „ 没有重复关键码的情况，需要n个不 同的编码来表示它们 „ 也就是说，d>=logr n，即在Ω(log n)中 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 165 小结 „ 7.1 基本概念 „ 排序码、正逆序、稳定性 „ 7.2 三种Ｏ(n2)的简单排序 „ 比较次数、移动次数（交换vs移动） „ 7.3 Shell排序 „ 7.4 基于分治法的排序 „ 快速排序、归并排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 166 „ 7.5 堆排序 „ 选择排序 „ 7.6 分配排序和基数排序 „ 链表、地址排序 „ 7.7 排序算法的理论和实验时间代价 „ 判定树 END!