数据结构知识点总结（详细无题目）(4)

归并排序 稳定 O(nlbn) O（n*n） O（nlbn） O（nlbn） O（n*n） O（nlbn） O（n） O（1） O(1) 简单选择排序 稳定 堆排序 基数排序 不稳定 稳定 O（d（n+rd）） O（d（n+rd）） O（rd） ? 选取排序方法需要考虑的因素： (1) 待排序的元素数目n； (2) 元素本身信息量的大小； (3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。 ? 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于\比较\的排序算法，至少需要O(nlog2n)的时间。 ?

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构知识点总结（详细无题目）(4)在线全文阅读。