数組规模 M|10正序10k逆序 数组规禛 10K M10K正序10K逆序 童插入排序001421.3909 快道排序 0.0000360.0630.8280.004530.00437 优六序0:00 0.71I61 0.000321.42843 优化快遠排序0000090.00470.7190.03280.0328 分插入排序0000300.1139 000360.22781 归并排序 0.0000380.00720.937 0.00438 冒泡排序 000021722545 139863.184 优化归并排序0.0001005.7970.002210.00438 优化冒泡排序0.00021722477 000031224063 0.000190.00660.9320.005650.00586 选择排序 0.00014713853 1398911.42812 基数排序210.00389.02362.4220.026720.02359 She排序(2)|000410.013036680.003910065 基数排序40.000200.01191.2190.0121900171 She排序(3)0.0004110.01233.29 0002350.00547 基数排序80.00010.00910.766000510.005 张帖闻 T 上大带一储写 有,斩邮务究 78排序问题的下限 判定树( Dicision tree 排序问题的时间代价在9(m起码MO m判定树中叶结点的最大深度就是 时间)到o( n log n)(平均,最差情况) 排序算法在最差情况下需要的最 间 大比较次数 ■基于比较的排序算法的下限也为 e (n log n) 叶结点的最小深度就是最佳情况 下的最小比较次数 京大管息张铭编写 莉命究 北真大张写 用判定树模拟基于比较的排序 基于比较的排序的下限 ■对n个记录,共有n!个叶结点 判定树的深度为og(n! CCAcB 在最差情况下需要log(m小次比较 即(n·logm 画 ■在最差情况下任何基于比较的排序 算法都需要9( nlog n)次比较 真大带息学张铭端写 ,命究 北真大脆张铭编写27 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 157 选择排序 0.000147 1.3853 _____ 1.39891 1.42812 Shell排序(2) 0.000044 0.0130 3.668 0.00391 0.00625 优化冒泡排序 0.000217 2.2477 _____ 0.00031 2.24063 Shell排序(3) 0.000041 0.0123 3.297 0.00235 0.00547 冒泡排序 0.000217 2.2545 _____ 1.3986 3.1184 二分插入排序 0.000030 0.1139 _____ 0.0036 0.22781 优化插入排序 0.000075 0.7161 _____ 0.00032 1.42843 直接插入排序 0.000142 1.3909 _____ 0.00032 2.76891 数组规模 100 10K 1M 10K正序 10K逆序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 158 快速排序 0.000036 0.0063 0.828 0.00453 0.00437 优化快速排序 0.000019 0.0047 0.719 0.00328 0.00328 数组规模 100 10K 1M 10K正序 10K逆序 基数排序/8 0.000077 0.0059 0.766 0.0075 0.0075 基数排序/4 0.000120 0.0119 1.219 0.01219 0.01172 基数排序/2 0.000238 0.0236 2.422 0.02672 0.02359 堆排序 0.000019 0.0066 0.932 0.00565 0.00586 优化归并排序 0.000027 0.0053 0.797 0.00422 0.00438 归并排序 0.000038 0.0072 0.937 0.005 0.00438 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 159 7.8 排序问题的下限 „ 排序问题的时间代价在Ω(n)(起码I/O 时间) 到O(n log n) (平均, 最差情况) 之间 „ 基于比较的排序算法的下限也为 Θ(n· log n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 160 判定树( Dicision Tree ) „ 判定树中叶结点的最大深度就是 排序算法在最差情况下需要的最 大比较次数 „ 叶结点的最小深度就是最佳情况 下的最小比较次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 161 用判定树模拟基于比较的排序 A<B<C A<C<B C<A<B B<A<C B<C<A C<B<A A<B<C A<C<B C<A<B A<B B<A<C B<C<A C<B<A B<A A<C C<A<B C<A C<B B<A<C B<C<A C<B<A B<C C<B A<C C<A A<B<C A<C<B B<C B<A<C B<C<A A<B<C A<C<B 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 162 基于比较的排序的下限 „ 对n个记录，共有n!个叶结点 „ 判定树的深度为log(n!) „ 在最差情况下需要log(n!)次比较， 即Ω(n· logn) „ 在最差情况下任何基于比较的排序 算法都需要Ω(nlog n)次比较