★ 基于“比较”操作的内部排序性能大PK
我们首先总结一下《排序结构专题1-4》中的十种方法的性能((N个关键字的待排序列)):
排序方法
|
平均时间
|
最坏时间
|
辅助存储空间
|
稳定性
|
直接插入排序
|
O(N^2)
|
O(N^2)
|
O(1)
|
√ |
折半插入排序 |
O(N^2) |
O(N^2)
|
O(1)
|
√ |
希尔排序
|
O(N*logN) |
O(N*logN) |
O(1)
|
× |
起泡排序 |
O(N^2) |
O(N^2) |
O(1) |
√
|
快速排序 |
O(N*logN) |
O(N^2) |
O(logN) |
× |
简单选择排序 |
O(N^2) |
O(N^2) |
O(1) |
√
|
树形选择排序 |
O(N*logN) |
O(N*logN) |
O(N) |
√ |
堆排序 |
O(N*logN) |
O(N*logN) |
O(1) |
× |
归并排序 |
O(N*logN)
|
O(N*logN)
|
O(N) |
√
|
1、 O(N^2)
级别的普通排序算法,我们用C++
的随机函数rand()
产生的随机数进行排序,并计算耗费时间。
其中分别随机生成1W,3W,5W... 19W(增量为2W)共十组待排序列进行测试。得到直接插入排序、折半插入排序、起泡排序、简单选择排序的耗时统计图如下所示(SPSS软件做图统计)。
从上图可以发现,起泡排序的耗时最大,其他三者的耗时差不多。其中折半插入排序在待排数据量达到19W以后,其性能要比直接插入排序,和简单排序要好一些。另外,在数据量较小的情况下,插入排序的性能要比选择排序要略好。
普通算法分析:在数据规模较小时(9W之内),折半插入、直接插入、简单选择插入差不多。当数据量较大时,折半插入要好一些。而起泡排序算法的时间代价是最昂贵的。
另外,普通排序算法基本上都是相邻元素进行比较,因此O(N^2)基本的排序算法都是稳定的。
2、O(N*logN)
级别的先进排序算法,其时间复杂度要比普通算法要快得多。由于数据本身要小的多,因此我们没有拿它们和普通算法进行比较,而是另外选择从10W——140W(增量10W)的15组数据进行测试,耗时性能比较如下(SPSS软件做图统计):
从上图可以发现,先进排序的耗时代价远远小于普通排序算法。而先进算法之间也有区别。其中快速排序无疑是最优秀的。其次是归并排序和希尔排序,堆排序稍微差一些,而最差的就是树形选择排序了。
先进算法分析:
(1) 就时间性能而言,
希尔排序、快速排序、树形选择排序、堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。
(2) 先进算法之中,快排的效率是最高的。
但其缺点十分明显:在待排序列基本有序的情况下,会蜕化成起泡排序,时间复杂度接近
O(N^2)。
(3) 希尔排序的性能让人有点意外,这种增量插入排序的高效性完全说明了:在基本有序序列中,直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案,要知道增量的选取直接影响排序的效率。
(4) 归并排序的效率非常不错,在数据规模较大的情况下,它比希尔排序和堆排序都要好。
(5)堆排序在数据规模较小的情况下还是表现不错的,但是随着规模的增大,时间代价也开始和上面两种排序拉开的距离。
(6)树形选择排序并不是较好的先进排序方法,数据规模越大,其耗时代价越高。而且它所需要的额外辅助空间较多,达到O(N)级别。想想看,排序140W数据,需要额外再开辟140W的空间,实在是无法忍受。
(7) 多数先进排序都因为跳跃式的比较,降低了比较次数,但是也牺牲了排序的稳定性。
总的来说,并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见:
(1) 数据规模很小,而且待排序列基本有序的情况下,选择直接插入排序绝对是上策。不要小看它O(N^2)级别。
(2) 数据规模不是很大,完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心),快排永远是不错的选择,当然付出log(N)的额外空间是值得的。
(3) 海量级别的数据,必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法。
附:以上两个图的数据测试在Pentium 4 CPU 3.06GHZ下,CPU占用率0%的情况下运行的结果。
另外,下面是我测试九种排序算法的C源代码,可供大家下载使用。
★ 一个关于O(N*logN)耗时下限的理论
这里有一个疑问:是不是O(N*logN)是排序算法时间代价最好的极限呢?
当然不是,但是如果排序算法是基于"关键字比较"操作的,那么在最坏情况下确实能够到达的最好效果就是O(N*logN)了。
在最好情况下就没必要说了,如果待排序列基本有序,那么直接插入排序的比较次数都非常的少。
下面我们来证明一下(注意:这些排序算法的基本操作就是比较,其时间主要消耗在比较次数上)。现在有三个关键字K1、K2、K3。那么下图给出了这三个关键字记录在任何可能的排序状态下的判定树,树中的内部结点都进行了一次必要的比较。
三个关键字的待排序列只有上面叶子结点所描述的6中排序状态。而判定树上的每一次比较都是必须的。因此、这个判定树足以描述通过“比较”进行的排序过程。并且,每一个待排序列经过排序达到有序序列所需要进行的"比较"次数,恰为从树根到叶子结点的路径长度。因此3个关键字的比较最少需要2次,最多需要3次。
扩展一下,有N个关键字序列。那么就有N!种排序状态,自然判定树就有N!个叶子节点。我们知道,二叉树的树高为h的情况下,叶子结点最多有2^(h-1)个。而现在又N!个叶子结点,那么树高至少为log(N!)+1。也就是说,描述N个记录排序的判定树必存在一条长度为[log(N!)+1]的路径。根据斯特林公式(n!的高精度近似求解公式): log(N!)=N*log(N)。因此,最少的比较次数也就是N*log(N)了。
基于比较操作的排序算法的时间复杂度下限确实是O(N*logN)。那么如果不比较呢,耗时代价会不会进一步减少。当然,关于这方面的排序算法,请见《桶排序
》、《基数排序
》。
分享到:
相关推荐
数据结构中基于分治策略的排序算法探讨数据结构中基于分治策略的排序算法探讨
对数据元素集合建立某种有序排列的过程称为排序。本章主要介绍一些常用的排序算法:...这里介绍的排序算法都是基于待排序的数据元素序列构成的线性表采用顺序存储结构,即采用数组存储,并且默认为按关键字非递减排序
是基于数据接结构中的内部排序编写的一个程序。通过比较各个内部排序之间的时间福复杂度来判断个算法之间的优劣。
快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; 堆排序 : 如果内存空间允许且要求稳定性的, 归并排序:它有一定数量的数据移动,所以我们...
算法根据大规模数据内部全局流形结构进行排序,提高了排序结果的准确性。在人类和按蚊全基因组范围内的实验证明,流形排序算法的预测效果优于传统的预测方法,可以作为预测miRNA的一个有效工具。
根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序。 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程;外部排序指的是待排序的记录数量很大,以致内存一次不能容纳...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
第3篇 基于对象的程序设计 第8章 类和对象 8.1 面向对象程序设计方法概述 8.1.1 什么是面向对象的程序设计 8.1.2 面向对象程序设计的特点 8.1.3 类和对象的作用 8.1.4 面向对象的软件开发 8.2 类的声明和对象的定义...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
二、 内部排序 1. 算法设计与分析题:将直接插入排序的内循环改造为使用对分查找实现元素插入,请写出基于对分查找的插入排序算法并给出其时间复杂度分析。 2. 算法设计:将教案给出的非递归直接插入排序和冒泡排序...
二、内部排序 1.算法设计与分析题:将直接插入排序的内循环改造为使用对分查找实现元素插入,请写出基于对分查找的插入排序算法并给出其时间复杂度分析。 2.算法设计:将教案给出的非递归直接插入排序和冒泡排序算法...
第5章探讨了两种经典的数据结构:堆栈和队列。本章节强调的重点是这些数据结构在解决日常数据处理问题中的实际应用。第6章讲述了BitArray类。这种类可以用于有效地表示大量整数值,比如测试成绩。 数据结构的书中...
第3篇 基于对象的程序设计 第8章 类和对象 8.1 面向对象程序设计方法概述 8.1.1 什么是面向对象的程序设计 8.1.2 面向对象程序设计的特点 8.1.3 类和对象的作用 8.1.4 面向对象的软件开发 8.2 类的声明和对象的定义...
*本框架内部已实现多个基本数据类型的排序器 组件包括:整数\小数\文本\字节集\日期时间等排序器,对于自定义数据类型,开发者通过继承“抽象排序器”类,并实现5个简单的抽象方法(子类重写“抽象排序器”类中以...
//C++实现基于多态的职工管理系统 //管理系统实现功能: //1.退出当前管理系统 //2.增加职工信息:实现批量添加职工功能,将信息录入到文件中,职工信息为:职工编号,职工姓名,部门编号 //3.显示职工信息:显示...
这些操作是基于这个项的,例如修改项、查找项中的些细节或者对项中的-些内容进行排序。当明确指定这些操作之后,就可以开始实现这个程序了。实现决定应该使用哪种数据结构,从而达到更好的时间以及空间执行效率。...
依据同构化基本原理,研究和发现了基于传统内部首尾排序算法的同构化特点与本质;进而,利用其同构化特点与本质,提出了几种基于链表的首尾排序新算法;从而,进一步深化和推广了首尾排序算法的应用方式与实用范围;...