Localhost8080

内部排序方法的分析比较

以上综述了各种排序方法的基本排序思想，使读者更进一步熟悉和掌握这些排序方法及排序过程。下面对这些排序方法从几个方面进行分析比较。
　　
1．时间复杂度


　　① 直接插入、直接选择、冒泡排序算法的时间复杂度为(n²)；

　　② 快速、归并、堆排序算法的时间复杂度为O(nlog₂n)；

　　③ 希尔排序算法的时间复杂度很难计算，有几种较接近的答案：O(nlog₂n)或O(n^1.25)；
　　④ 基数排序算法的时间复杂度为O(d*(rd+n)),其中rd是基数，d是关键字的位数，n是元素个数。


2．稳定性


　　① 直接插入、冒泡、归并和基数排序算法是稳定的；
　　② 直接选择、希尔、快速和堆排序算法是不稳定的。


3．辅助空间（空间复杂度）


　　① 直接插入、直接选择、冒泡、希尔和堆排序算法需要辅助空间为O(1)；
　　② 快速排序算法需要辅助空间为O(lgn)；
　　③ 归并排序算法需要辅助空间为O(n)；
　　④ 基数排序算法需要辅助空间为O(n+rd)。


4．选取排序方法时需要考虑的主要因素有：


　　① 待排序的记录个数；
　　② 记录本身的大小和存储结构；
　　③ 关键字的分布情况；
　　④ 对排序稳定性的要求；
　　⑤ 时间和空间复杂度等。


5．排序方法的选取


　　① 若待排序的一组记录数目n较小(如n≤50)时，可采用插入排序或选择排序。
　　② 若n较大时，则应采用快速排序、堆排序或归并排序。
　　③ 若待排序记录按关键字基本有序（正序或叫升序），则适宜选用直接插入排序、冒泡排序或快速排序。
　　④ 当n很大，而且关键字位数教少时，采用链式基数排序较好。
　　⑤ 关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。


6．排序方法对记录存储方式的要求：


　　① 当记录本身信息量较大时，插入排序、归并排序、基数排序易于在链表上实现；
　　② 快速排序、堆排序更适合用索引结构上排序；
一般的排序方法都是在顺序结构（一维数组）上实现。

posted on 2010-10-29 00:12 superKiki 阅读(555) 评论(0)  编辑 收藏 引用