数据结构:各种排序方法的综合比较
排序方法的选用应视具体场合而定。一般情况下考虑的原则有:(1)待排序的记录个数 n;(2)记录本身的大小;(3)关键字的分布情况:(4)对排序稳定性的要求等。
1.时间性能
(1) 按平均的时间性能来分,有三类排序方法:
时间复杂度为 O(nlogn)的方法有:快速排序、堆排序和归并排序,其中快速排序目前被认为是最快的一种排序方法,后两者比较,在n值较大的情况下,归并排序较堆排序更快。
时间复杂度为 O(n2)的有:插入排序、起泡排序和选择排序,其中以插入排序为最常用,特别是对于已按关键字基本有序排列的记录序列尤为如此,选择排序过程中记录移动次数最少。
时间复杂度为 O(n)的排序方法只有基数排序一种。
(2) 当待排记录序列按关键字顺序有序时,插入排序和起泡排序能达到 O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为 O(n2),因此应尽量避免。
(3) 选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变在大多数情况下,人们应事先对要排序的记录关键字的分布情况有所了解,才可对症下药,选择有针对性的排序方法。
(4) 以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数,当待排序记录中其他各数据项比关键字占有更大的数据量时,还应考虑到排序过程中移动记录的操作时间,有时这种操作的时间在整个排序过程中占的比例更大,从这个观点考虑,简单排序的三种排序方法中起泡排序效率最低。
2.空间性能
空间性能指的是排序过程中所需的辅助空间大小。
(1) 所有的简单排序方法(包括: 插入、起泡和选择排序)和堆排序的空间复杂度均为O(1)
(2) 快速排序为 O(logn),为递归程序执行过程中栈所需的辅助空间
(3) 归并排序和基数排序所需辅助空间最多,其空间复杂度为 O(n)。
3.排序方法的稳定性能
(1) 稳定的排序方法指的是对于两个关键字相等的记录在经过排序之后,不改变它们在排序之前在序列中的相对位置。
(2) 除快速排序和堆排序是不稳定的排序方法外,其他排序方法都是稳定的。例如:对关键字序列(41,3,42,2)进行快速排序,其结果为(2,3,42,41)。
(3)“稳定性”是由方法本身决定的。一般来说,排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间,没有大步距的数据调整时,则排序方法是稳定的。
综合上述,可得下表:
由此,在选择排序方法时,可有下列几种选择:
(1) 若待排序的记录个数 n值较小(例如 n<30),则可选用插入排序法,但若记录所含数据项较多,所占存储量大时,应选用选择排序法。反之,若待排序的记录个数n值较大时应选用快速排序法。但若待排序记录关键字有“有序”倾向时,就慎用快速排序,而宁可选用归并排序或堆排序。
(2) 快速排序和归并排序在 n 值较小时的性能不及插入排序,因此在实际应用时,可将它们和插人排序“混合”使用。如在快速排序划分子区间的长度小于某值时。转而调用插入排序;或者对待排记录序列先逐段进行插入排序,然后再利用“归并操作”进行两两归并直至整个序列有序为止。
(3) 基数排序的时间复杂度为 O(dXn),因此特别适合于待排记录数 n 值很大,而关键字“位数 d”较小的情况。并且还可以调整“基数”(如将基数定为 100 或 1000 等)以减少基数排序的趟数 d 的值。
(4) 一般情况下,进行排序的记录的“排序码”各不相同,则排序时所用的排序方法是否稳定无关紧要。但在有些情况下的排序必须选用稳定的排序方法。例如,一组学生记录已按学号的顺序有序,由于某种需要,希望根据学生的身高进行一次排序,并且排序结果应保证相同身高的同学之间的学号具有有序性。显然,在对“身高”进行排序时必须选用稳定的排序方法。
相关文章
- java基础知识回顾之---java String final类普通方法的应用之字符串数组排序
- 去除inline-block元素间间距的N种方法
- 【MySQL】Got fatal error 1236原因和解决方法
- Python生成随机数组的方法小结
- 使用Sort方法对数组进行快速排序
- file.listFiles()按文件大小、名称、日期排序方法
- Linux下强制杀死进程的方法
- Spring3数据源的6种配置方法
- TreeSet的两种排序方法
- tp5 中文排序失效解决方法convert(name USING gbk)
- SAP UI5 视图控制器 View Controller 的生命周期方法 - Lifecycle methods
- Java 8里一元函数Function的compose和andThen方法区别
- Atitit 知识与数据 信息 加工方法总结 目录 1.1. 信息加工是指通过判别、筛选、分类、排序、分析和研究等一系列过程1 1.2. 多种聚合方法1 2. 首先通过聚类信息 专题化 分组聚
- Atitit.现实生活中最好使用的排序方法-----ati排序法总结
- List集合序列排序的两种方法
- JavaScript数组的常用方法总结:遍历,复制,反转,排序,添加,删除(前端常见面试题必考必问)实例演示
- Python语言学习:复杂函数(yield/@property)使用方法、案例应用之详细攻略
- Lombok的@Data生成的hashCode和equals方法坑
- 排序链表-c语言常规方法,数组存储加快速排序
- 习题 6.20 用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个函数。整数和n在主函数中输入。最后在主函数中输出。
- 例 8.10 用指针方法对10个整数按由大到小顺序排序。
- 【Groovy】MOP 元对象协议与元编程 ( 使用 Groovy 元编程进行函数拦截 | 使用 MetaClass 进行方法拦截 | 对象上拦截方法 | 类上拦截方法 )
- Linux命令 -- 查看系统版本的各种方法
- CSharpGL(36)通用的非托管数组排序方法
- 对于多个button要在同一个监听器中实现自己的单击事件的方法小诀窍。
- C++ 排序函数 sort(),qsort()的使用方法
- Linux centos7新建Oracle数据库,在进度条百分之六十八的时候报错ins_ctx.mk编译错误的解决方法
- JavaScript数组的常用方法总结:遍历,复制,反转,排序,添加,删除(前端常见面试题必考必问
- 第十七篇:汇总,删除String中的指定字符的11种方法
- 【看表情包学Linux】探讨项目构建问题 | Makefile | 依赖关系与依赖方法 | 伪目标 PHONY