ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 效率神器,一键搞定繁琐工作
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 63091|回复: 116

[原创] 有史以来最快的希尔排序 - 比历史贴快10倍,比Excel排序更快 - 兼论堆排序和快速排序

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2010-12-13 19:47 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:排序
本帖最后由 灰袍法师 于 2011-9-13 17:15 编辑

希尔排序对 未排序数据的顺序 不敏感,虽然平均而言速度比快速排序慢一倍左右

但是却安全很多,没有快速排序的堆栈溢出问题,没有退化为O(n^2)的问题

而且对比较有序的输入数据,重复度高的数据,速度远远超过快速排序。

所以还是一个很不错的排序算法,尤其是还可以跟快速排序结合,大大降低快速排序的递归次数。

希尔排序实现起来比也非常简单。就是多重循环比较不好看而已。

附件的希尔排序已经做成一个子程序,在任何程序直接调用即可。

希尔排序的速度关键是:选择合适的h序列,也就是每次循环跳过多少个数据来交换

论坛以前的贴,都完全没有注意选择好的h序列,所以速度极慢,根本无法排序千万级别的数据。

作为刚学习排序算法的参考资料还可以,作为实际使用的排序代码则悲剧。

本附件可以用于过千万数据的排序,因为目前排序100万数据,三千万次操作,大概是6秒,增长阶又确定是O(n^1.25)

那么 1000万数据也只不过5.6亿操作,多用18倍时间,两分钟内完成。实际上我的电脑是65秒排序1000万随机变体类型整数

再啰嗦一下h序列的问题,假设已经知道希尔排序使用的h序列是怎么回事

那么比较常用的,已经经过计算机界的大师验证,绝对慢不到哪里去的h序列,有以下几种
1 h1=1, 然后往后每个h都等于 3h+1

2 h1=1, 然后往后每个h都等于 2.25h+1,取整

3 这个比较复杂, h1当然也是1,h2往后则用公式计算出来,假如
[n]是单数,那么 h[n] =8*2^n-6*2^((n+1)/2)+1
[n]是双数,那么 h[n] =9*2^n-9*2^(n/2)+1
也就是说 h序列 = {1,,5,19,41,109,209,505,929,........}
这一个序列已经被数学证明为O(n^1.25)的增长阶,证明过程则估计我完全看不懂。。。。。。

4 我自己的发现,由于h序列一般来说,前后两个h是互质的会比较好,而我又发现3号序列并不完全是质数
于是就把所有的非质数换为最接近的质数,结果发现又快了3%左右,yeah! 这也是我的附件代码最终采用的h序列

论坛以前发过的希尔排序贴,貌似都是用 h[n] = 2^n - 1,或者干脆就是 h[n] = 2^n

前者貌似也是O(n^1.25),但是明显比前面四个序列慢一大截

后者则是算法发明人希尔最早提出的序列,但是很快就被证明是个非常坏的h序列,速度慢而且很可能会退化到O(n^2),所以不宜采用。

*************************************以下讨论堆排序
堆排序的速度,一般比希尔排序慢10%到20%

基本的堆排序,速度很慢,原因是每次交换最大的元素到数组末尾,这时候数组末尾的元素将交换到堆顶

再次把这个元素放进堆里面,就是把一个很小的元素压进堆,比较的次数将会很多,几乎必定是log(n)

所以采用Floyd的算法,先把这个很小的堆顶元素压到最底层,然后再上升到合适位置,这样就可以加快一倍

附件是四个堆排序算法:分别是最基本的堆排序,三元分叉的堆排序,最基本堆排序+先沉底再上升(最佳版本),三元的堆排序+先沉底再上升

可以看出,基本三元堆比基本两元堆快,而且先沉底再上升的做法,对三元堆,两元堆都有效

而令人惊奇的是:两元堆先沉底再上升,比三元堆先沉底再上升更快,可能是三元堆提升三个叶子的最大元素,其比较次数太多

这倒是件好事,因为两元堆的代码比较简单,而且速度更快,好极了。

堆排序最大特点:可以迅速取出最大值(或者最小值),如果是求100万元素的前1万个,那么堆排序肯定是最快的。

因为只需要对1万个元素进行堆处理,而其它排序方法需要对100万个元素排序。

嗯。。。。。。也许快速排序也可以缩小排序的范围,如超过1万的部分就不再递归排序,也许还有可能比堆排序快。

*************************************以下讨论快速排序
作为一般而言最高速的排序算法,快速排序既让人高兴,又让人不放心

高兴的是:速度真的快多了

不放心的是:碰到某些序列,排序时间会恶化到无法接受的O(n^2)

附件是六个版本的快速排序,基本上包括了对快速排序进行优化的各种技巧

作为对比,第一个最慢速最不可靠的版本是从论坛帖“七种排序算法”抄过来的

其余五个版本是我自己的作品

简而言之,快速排序的弊端是

1 递归次数太多,会导致堆栈空间溢出。
解决办法:对小于一定数量的元素进行直接插入排序,希尔排序,而不是留给下一层的递归快速排序

2 每次划分的枢纽值选取不当,就会大大影响速度
解决办法:用平均值,随机值等等方式来决定枢纽值,但是无法保证一定不会出现速度退化的现象
进一步解决方法:先用快速排序,然后如果超过一定时间,或者递归一定次数后还没完成,就完全转为希尔排序。

综合而论,我个人觉得还是希尔排序最可靠,堆排序由于每次都取出最大值的特点,有些时候是非它不可!

快速排序单纯用原始版本,是一个又慢又危险的算法,完全没有任何价值

改良以后速度极好,但不能完全放心,辅以希尔排序才是王道。

补充汉字的排序方式:
Excel本身的sort方法,有两种汉字排序方式
名称 值 描述
xlPinYin 1 按字符的汉语拼音顺序排序。这是默认值。  
xlStroke 2 按每个字符的笔划数排序。

VBA里面,字符串比大小也有两种方式
option compare binary 对应按笔画数排序(默认值)
option compare text 对应按拼音排序,速度大概慢一倍吧

本附件全部按option compare binary,也就是按笔画数排序,如果不合要求,那么自己在代码加上 option compare text即可改为按拼音排序。
[ 本帖最后由 灰袍法师 于 2011-2-16 22:13 编辑 ]


补充内容 (2013-7-30 21:53):
强烈推荐 lee1892 的排序贴。
http://club.excelhome.net/thread-1004590-1-1.html

VBA - 排序算法 - 希尔排序 O1.25阶 - 更好的互质序列.rar

37.97 KB, 下载次数: 2006

VBA - 排序算法 - 堆排序.rar

77.98 KB, 下载次数: 1179

六个版本的快速排序.rar

105.54 KB, 下载次数: 1855

评分

16

查看全部评分

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:03 | 显示全部楼层
谢谢分享!!

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:09 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
支持原创!向老师学习!

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:11 | 显示全部楼层
提示:变量未定义,光标指向SortOn:=xlSortOnValues

    ActiveWorkbook.Worksheets("Sheet1").Sort.SortFields.Add Key:=Columns("A:A"), _
        SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal

把上面这句注释后,逐句运行
到  ActiveWorkbook.Worksheets("Sheet1").Sort.SortFields.Clear又不行,提示 对象不支持该属性或方法


2003版

[ 本帖最后由 smhf_6 于 2010-12-13 20:23 编辑 ]

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:12 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:19 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
论坛的法师确实厉害,要做成VB大法必须请法师出马才行.

TA的精华主题

TA的得分主题

 楼主| 发表于 2010-12-13 20:27 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
原帖由 smhf_6 于 2010-12-13 20:11 发表
提示:变量未定义,光标指向SortOn:=xlSortOnValues

    ActiveWorkbook.Worksheets("Sheet1").Sort.SortFields.Add Key:=Columns("A:A"), _
        SortOn:=xlSortOnValues, Order:=xlAscending, DataOption: ...


哎,又是录制宏的问题

你自己录制一个对A列排序的宏好了

不过2003版本才几万行,速度差异几乎是看不出来的

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:30 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:40 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2010-12-13 20:47 | 显示全部楼层
学习了,看来数组功底好,是学好编程的最重要法宝。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-11-22 00:21 , Processed in 0.047665 second(s), 11 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表