|
|
本帖最后由 灰袍法师 于 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 |
评分
-
16
查看全部评分
-
|
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2010-12-13 19:47
发表于 2010-12-13 20:19
楼主
