`

【排序结构5】 基于比较的内部排序总结

阅读更多

★ 基于“比较”操作的内部排序性能大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)。那么如果不比较呢,耗时代价会不会进一步减少。当然,关于这方面的排序算法,请见《桶排序 》、《基数排序 》。

 

 

 

 

2
0
分享到:
评论
2 楼 bravelinw 2013-12-25  
[size=xx-small]大牛果然牛掰[/size]
1 楼 worldterminator 2013-08-29  
shell sort O(nlogn)?
在哪看的? 最坏情况是 n^2

相关推荐

    命令手册 Linux常用命令

    命令手册 Linux常用命令

    【超强组合】基于VMD-雪融优化算法SAO-Transformer-GRU的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【超强组合】基于VMD-花朵授粉优化算法FPA-Transformer-BiLSTM的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    基于SpringBoot+Shiro+mysql实现的个人博客前后台管理系统 【完整源码+数据库】

    一、功能描述 文章管理 分类管理 评论管理 数据库监控 通用页面 后台首页 友链管理 在线用户 权限管理 角色管理 站点管理 标签管理 主题管理 上传管理 用户管理 踢出页面 登录页面 注册页面 主题目录 默认主题 二、技术栈 Spring Boot、Apache Shiro、MyBatis-Plus、Alibaba Druid、Redis、MySQL、Thymeleaf 三、安装 将本项目源码导入本地开发工具(如 IntelliJ IDEA ),本地开发工具需要安装 lombok 插件 安装Mysql数据库:Mysql版本最低支持5.7,新建 database CREATE DATABASE pb_cms_base; 初始化数据库:找到项目数据库文件:docs/db/pb_cms_base.sql,执行 pb_cms_base.sql 前台首页,浏览器访问http://localhost:8080 后台首页,浏览器访问http://localhost:8080/admin使用账号密码admin,123456登录系统后台。

    暴风电视刷机 T55FUA 通用ECHO 屏ST5461D07-2 机编60000AM6400 AM6700 V1.0.03版本

    务必确认机身编号与文件名机编一致,如不一致,请勿下载 机身编号一般在机子背面的贴纸上 适配屏参:30164505 MSD6A838平台升级步骤 强制升级(不开机强制升级): 1、下载数据,压缩包解压,将BFTVUpdate838_xx.bin拷贝至U盘根目录下,插入电视USB端口 2、插拔下电源,按一下遥控器待机键后快速不停的点按遥控器上键触发主板识别U盘软件进行升级 3、升级成功需运行至100%,此时耐心等待电视自动操作,切勿断电或拔掉U盘 4、系统升级后第一次重启系统需要3分钟左右,属于正常现象,切勿断电 升级完成后可以在系统设置——本机信息——查询软件版本更新状态 注意: 1、U盘要求使用FAT32格式,建议4G-8G的品牌U盘,刷机成功率会高 2、升级到结束,大约需要8-30分钟,中途绝对不能断电 3、升级重启第一次进入系统,请等完全正常进入开机桌面之后,才能拨下U盘 4、如无法升级,将BFTVUpdate838_xx.bin文件重命名为BFTVUpdate838.bin,再尝试刷机

    wryh+pico12num.ttf

    wryh+pico12num.ttf

    性能优化与加载时间控制.docx

    性能优化与加载时间控制.docx

    【数据分析】基于matlab数据流分类的双模型半监督自组织模糊推理系统【含Matlab源码 9067期】.zip

    CSDN海神之光上传的代码均可运行,亲测可用,直接替换数据即可,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描博客文章底部QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

    【超强组合】基于VMD-黑猩猩优化算法Chimp-Transformer-LSTM的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    ubuntu系统下,很好用的多线程下载工程 类似于windows系统下的迅雷

    使用时,稍研究即可。

    基于java+swing+applet实现的家庭理财系统(含源码+数据库+答辩PPT)

    基于java Swing+applet实现的家庭理财系统(含源码+数据库+答辩PPT)

    HCIE-IPv6技术

    HCIE-IPv6技术

    【超强组合】基于VMD-粒子群优化算法PSO-Transformer-GRU的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    数据可视化驾驶舱,包含地图,页面可以直接运行

    数据可视化驾驶舱,包含地图,页面可以直接运行

    【java毕业设计】师生交流平台源码(ssm+jsp+mysql+说明文档+LW).zip

    功能说明: 功能:个人中心、学生信息管理、教师信息管理、教学资源管理、教学反馈管理、教学答疑管理、作业发布管理、作业管理、我的收藏管理、管理员管理、留言板管理、论坛管理、系统管理模块。 环境说明: 开发语言:java 框架:ssm jdk版本:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse 部署容器:tomcat7+

    动态加载的性能影响与优化.docx

    动态加载的性能影响与优化.docx

    【超强组合】基于VMD-蛇群优化算法SO-Transformer-LSTM的光伏预测算研究Matlab实现.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    网络优化基础理论.docx

    网络优化基础理论.docx

    AI进展下ChatGPT对文献情报工作的影响及启示

    内容概要:报告讨论了ChatGPT这一人工智能对话系统的最新进展及其核心技术体系,探讨了其对文献情报工作带来的深远影响,提出了相应的应对策略。主要内容涵盖ChatGPT的定义与关键技术、人工智能发展的启示、ChatGPT的具体影响及文献情报领域的未来展望和建议。 适合人群:从事或关心文献情报工作、自然语言处理、人工智能研究的学者及从业人员。 使用场景及目标:旨在帮助相关从业者理解和把握ChatGPT带来的变化,调整和完善工作流程,提高文献情报服务质量。适用于学术研究、技术创新等领域。 其他说明:文中提到了许多实例和具体措施,对于实际操作有着重要的指导意义。阅读者应该结合自身的工作情况,灵活运用这些建议。此外,报告呼吁业内专业人士积极合作,共同推进技术的应用和发展。

    【java毕业设计】致远汽车租赁系统源码(springboot+vue+mysql+说明文档+LW).zip

    功能说明: 管理员:管理员使用本系统涉到的功能主要有:首页,个人中心,用户管理,业务员管理,汽车类型管理,租赁汽车管理,汽车租赁管理,汽车归还管理,租赁订单管理,检查信息管理,系统管理等功能。 用户:用户使用本系统涉到的功能主要有:首页,个人中心,汽车租赁管理,汽车归还管理,租赁订单管理,检查信息管理,我的收藏管理等功能。 业务员:业务员使用本系统主要包括首页,个人中心,汽车租赁管理,汽车归还管理,租赁订单管理,检查信息管理等功能。 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse

Global site tag (gtag.js) - Google Analytics