当前位置:文档下载 > 所有分类 > 高等教育 > 工学 > 数据结构中排序总结
侵权投诉

数据结构中排序总结

排序的时间和空间复杂度分析

排序总结

排序方法 平均时间 最坏时间 辅助存储

简单排序 O(n2) O(n2) O(1)

快速排序 O(nlogn) O(n2) O(logn)

堆排序 O(nlogn) O(nlogn) O(1)

归并排序 O(nlogn) O(nlogn) O(n)

另外:直接插入排序、冒泡排序为简单排序,希尔排序(不稳定)

一、时间性能

按平均的时间性能来分,有三类排序方法:

时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;

时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为

最好,特别是对那些对关键字近似有序的记录序列尤为如此;

当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂

度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应

该尽量避免的情况。

第1页

免费下载Word文档免费下载:数据结构中排序总结

(下载1-3页,共3页)

我要评论

返回顶部