编程入门教程第十章 排序 - 图文

10.3.5树形选择排序133838493865659776131327132749493838653865977676∞272727274938383849386565977676∞∞4949494949∞6549659749497676∞∞4949ypb@ustc.edu.cn25中国科学技术大学10.4基数排序（复杂度O(d×n)）?逻辑关键字、关键字，关键字分级

?对于有d个关键字的记录排序，要进行d趟分配和收集?时间复杂度O(n×d);空间复杂度O(n)

待排关键字序列A关键字0123456787863303065736973899578698389659583B关键字306373839565788969100count10110024321034014265401506432160265471287682719893) 6)从后到前将从后到前将记录按累加值指示的地址复制到数组B中的记录依照BA1) 2) 4) 5) 对“个位数统计计算“累加值十位数”进行”各个取值的记录数“计数”“count”指示的地址复制到ypb@ustc.edu.cn26中国科学技术大学10.5各种排序的综合比较?选择排序方法考虑因素

–待排序记录数n

–记录本身其他信息量大小–关键字分布情况–稳定性要求?时间性能

–按时间性能分三类:简单、先进、基数–有序性对算法的影响

?插入和起泡有好的影响O（n）?快速有坏的影响O(n2)

?选择、归并、堆、基数没有影响

–记录其他信息复杂度对算法的影响

?起泡、快速、堆等移动较多的算法影响较大

ypb@ustc.edu.cn27中国科学技术大学?空间性能

–所有简单排序、堆是O（1）–快速是O（Logn）–归并、基数O(n)

?稳定性

–快速和堆大范围交换的算法不稳定–其他算法均稳定。

例：（4，3，4，2）进行快速排序不稳定?经过一趟排序能将一个数据放在最终位置

–选择、起泡、堆

ypb@ustc.edu.cn28中国科学技术大学