«December 2019»
1234567
891011121314
15161718192021
22232425262728
293031


公告

本站技术贴除标明为“原创”的之外,其余均为网上转载,文中我会尽量保留原作者姓名,若有侵权请与我联系,我将第一时间做出修改。谢谢!

             ——既瑜


天气预报(南京)


我的分类(专题)

首页(183)
【趣味文摘】(22)
【五子连珠】(13)
【技术文档】(136)
【电脑技术】(6)
【疑难问题】(1)
【我的心情】(5)


最新日志
花语(中英文对照版)
各种花的花语
NTFS格式的7个精彩问答(pconli
童言无忌,有趣得一蹋
给MM修电脑的三个步骤[转载]
J2EE 面试题综合
JAVA编程规则
[转] P2P之UDP穿透NAT的原理与
[转]词法分析器
文件加密技术
一个让人发狂的PI求解C程序
[转]直线生成算法之DDA
[转]利用内核对象----互斥量实现应用
[转]如何正确的计算文件收发进度
双机调试VC程序
[转]分治法优化大整数乘法 C++实现
浮点数值的内存结构
[转]双链表实现大整数的加法与乘法[VC
拜占廷将军问题[转]
某人的挂QQ的程序源代码,虽然没用了,拿

最新回复
回复:vc中的CString的操作
回复:[转]分治法优化大整数乘法 C++
回复:[转]分治法优化大整数乘法 C++
回复:花语(中英文对照版)
回复:基本排序算法比较与选择[转载]
回复:c++中强制类型转换操作符小结
回复:c++中强制类型转换操作符小结
何必那么执着于是大头猫还是愤怒的小鸟,淡
回复:浮点数值的内存结构
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:32位位图到24位位图的转换
dren, ages 16 and 20
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:各种花的花语

留言板
签写新留言

不是0-1背包喔
桂花的花语``
谢谢
提议
提议

统计
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1349176
建立时间:2005年3月12日

链接


http://www.nju.edu.cn
http://bbs.nju.edu.cn 
http://www.t7-online.com
http://www.csdn.net
http://www.91f.net
http://www.crsky.com
我的MSN BLOG 

联系我

  OICQ:215768265
  njucs2001@hotmail.com
  erichoo1982@gmail.com

 

W3CHINA Blog首页    管理页面    写新日志    退出


[【技术文档】]基本排序算法比较与选择[转载]
既瑜(224499) 发表于 2005-3-20 0:05:11

基本排序算法比较与选择 前几天应一个朋友的要求,帮他完成了数据排序的一个作业。觉得很有给大家参考的价值,所以经过他同意,作了些修改帖了上来。源代码见附件,代码中实现了8种排序算法,各算法名称见下表或见源码。运行程序时,将需要你输入一数值,以确定对多少随机数进行排序。然后将会显示各排序算法的耗时。并且你可选择时否进行正序和反序测试。 由于水平有限,可能存在一些错误,还请各位多多指点! 通过实验我们可将结果列入下表。 以下是VC6.0(Release)+win2000pro+128MDDR+P4(1.6G) 因为在多任务操作系统下,系统将进行进程序调度,影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值,我们得多次实验求其平均值。 排序算法实验比较(单位:秒) n 方法 1K 10K 100K 200K 100K 正序 逆序 冒泡排序 0 0.422 44.790 188.462 0 31.459 冒泡排序2 0 0.281 30.335 131.771 0 27.568 快速排序 0 0 0.016 0.047 5.095 7.002 直接选择排序 0 0.141 16.878 79.332 16.785 33.242 堆排序 0 0 0.031 0.109 0.031 0.015 直接插入排序 0 0.047 8.705 57.800 0 24.865 Shell排序 0 0 0.047 0.110 0.015 0.015 归并排序 0 0 0.031 0.094 0.032 0.032 基数排序 0 0 0.47 0.109 0.047 0.046 算法与结果联合分析 冒泡排序:在最优情况下只需要经过n-1次比较即可得出结果,(这个最优情况那就是序列己是正序,从100K的正序结果可以看出结果正是如此),但在最坏情况下,即倒序(或一个较小值在最后),下沉算法将需要n(n-1)/2次比较。所以一般情况下,特别是在逆序时,它很不理想。它是对数据有序性非常敏感的排序算法。 冒泡排序2:它是冒泡排序的改良(一次下沉再一次上浮),最优情况和最坏情况与冒泡排序差不多,但是一般情况下它要好过冒泡排序,它一次下沉,再一次上浮,这样避免了因一个数的逆序,而造成巨大的比较。如(2,3,4,…,n-1,n,1),用冒泡排序需要n(n-1)/2次比较,而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次,第一轮1将上移一位,第二轮1将移到首位,第三轮将发现无数据交换,序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法,只适合于数据基本有序的排序。 快速排序:它同样是冒泡排序的改进,它通过一次交换能消除多个逆序,这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下,它的排序时间复杂度为O(nlog2n)。即每次划分序列时,能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时,一串为空,另一串为m-1(程序中的100K正序和逆序就正是这样,如果程序中采用每次取序列中部数据作为划分点,那将在正序和逆时达到最优)。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢,这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”,在理论上讲,如果每次能均匀划分序列,它将是最快的排序算法,因此称它作快速排序。虽然很难均匀划分序列,但就平均性能而言,它仍是基于关键字比较的内部排序算法中速度最快者。 直接选择排序:简单的选择排序,它的比较次数一定:n(n-1)/2。也因此无论在序列何种情况下,它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多,相差的只是数据移动时间),可见对数据的有序性不敏感。它虽然比较次数多,但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。 堆排序:由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:-是建堆,二是排序(调整堆)。所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。 直接插入排序:简单的插入排序,每次比较后最多移掉一个逆序,因此与冒泡排序的效率相同。但它在速度上还是要高点,这是因为在冒泡排序下是进行值交换,而在插入排序下是值移动,所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较,在最坏情况下,将需要n(n-1)/2次比较。 希尔排序:增量的选择将影响希尔排序的效率。但是无论怎样选择增量,最后一定要使增量为1,进行一次直接插入排序。但它相对于直接插入排序,由于在子表中每进行一次比较,就可能移去整个经性表中的多个逆序,从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法,所以对数据有序敏感。 归并排序:归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。 基数排序:在程序中采用的是以数值的十进制位分解,然后对空间采用一次性分配,因此它需要较多的辅助空间(10*n+10), (但我们可以进行其它分解,如以一个字节分解,空间采用链表将只需辅助空间n+256)。基数排序的时间是线性的(即O(n))。由此可见,基数排序非常吸引人,但它也不是就地排序,若节点数据量大时宜改为索引排序。但基数排序有个前提,要关键字能象整型、字符串这样能分解,若是浮点型那就不行了。 按平均时间将排序分为类: (1) 平方阶(O(n2))排序  各类简单排序,例如直接插入、直接选择和冒泡排序; (2) 线性对数阶(O(nlog2n))排序  如快速排序、堆排序和归并排序; (3) O(n1+§))排序  §是介于0和1之间的常数。希尔排序便是一种; (4) 线性阶(O(n))排序  本程序中的基数排序,此外还有桶、箱排序。 排序方法的选择 因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法很重要(1)若n较小,可采用直接插入或直接选择排序。当记录规模较小时,直接插入排序较好,它会比选择更少的比较次数;但当记录规模较大时,因为直接选择移动的记录数少于直接插人,所以宜用选直接选择排序。这两种都是稳定排序算法。(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机,原因见上的快速排序分析);这里快速排序算法将不稳定。(3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。  归并排序是稳定的排序算法,但它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。(4)特殊的箱排序、基数排序它们都是一种稳定的排序算法,但有一定的局限性:  1、关键字可分解。  2、记录的关键字位数较少,如果密集更好  3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

阅读全文(25392) | 回复(13) | 编辑 | 精华

回复:基本排序算法比较与选择[转载]
要厚道(游客)发表评论于2011-8-11 11:46:38

转帖要注明出处和链接

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
等待夏天(游客)发表评论于2009-12-25 21:33:08

   我想看看代码 
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
renren(游客)发表评论于2009-10-12 8:57:13

ddsf
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
ZORO(游客)发表评论于2008-5-10 19:47:42

shell不是用的时间最少么?为什么不推荐shell??
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
uu(游客)发表评论于2008-2-11 7:04:11

源程序在你妈肚子里呢?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
为本(游客)发表评论于2007-12-12 19:55:02

fgfgfgfgfgfgfg
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
飞龙(游客)发表评论于2007-7-12 10:44:23

很不错
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
you ke(游客)发表评论于2007-2-13 12:41:39

乱写
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
无名(游客)发表评论于2007-1-1 18:12:49

我正在做这样差不多的作业,对我还是有参考价值的,不过我也想看看你的源代码,主要是算时间部分,我是一个初学者!!!!!!
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:基本排序算法比较与选择[转载]
shaufeng(游客)发表评论于2006-4-26 9:06:58

拜托不要乱写,误人子弟!
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

» 1 2 »

发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)

站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.063 second(s), page refreshed 144336120 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号