|
|
楼主 |
发表于 2011-3-31 23:40
|
显示全部楼层
原帖由 ningyuanchao 于 2011-3-31 21:52 发表 
请教灰袍法师：
希尔排序中有这么一句代码：
If h_arr(i) < (R - L) / 9 Then max_h = i
为什么是“9”，而不是其它数值，该如何选择？
9是我看的书的作者使用的数字，他没有说明原因，以下是我的理解：
9的作用是，对于最大的h，保证每次插入排序最少每组有9个key
如对100个key排序,那么h序列 temp_h = Array(1, 5, 19, 41, 109 ......
如果选择小于100的第一个数值41,那么第一次插入排序的跳跃步长是 41
这样一来每一组插入排序的key就只有2个，第一组是 1,42 第二组是2,43...... 最后一组是 41,82
而且最后的 83 - 100 这18个key将不会在第一遍插入排序出现
这显然是个低效的做法。
所以硬性规定每一组至少要有9个元素，这样我们得到的最大h是5，每一组插入排序有20个元素
第一组就是 1,6,11,16,21,26,31,......91,96
当然，9只是一个随便挑选的数字，一般来说 5-20都应该没啥问题，对于不同的待排序数据，设定不同的每组最小排序数量会导致速度略有差异
不过不明显，而且不可能有一个最优值，所以你大可以选择其它数字，只要相对于key的数量不是极端小，也不是极端大就可以了。
我个人的分析，考虑到插入排序的最坏情况是 O(n^2)，第一遍插入排序的元素绝对不能太多
如果第一组排序就是1万key，那么光是这第一次插入排序就可能导致 1万^2 = 1亿次 代码段循环，绝对不可接受！
所以很显然无论如何不应该大于1万，实际上即使是100，我也觉得不可接受，因为那就是1万次 代码段循环啦
9的话，顶多81，
对1000万key排序，第一遍每组排9个，要排111.111万组
另一方面，选择很小的数字如3，虽然每组插入排序的效率都肯定非常高，但是要进行的分组数就太多，所以得不偿失。。。。。。
平衡点肯定可以根据 内外两层代码的执行效率 计算出来
最内层代码 ： 对分组大小的一组进行插入排序耗时
外层代码 ：对所有key进行分组，然后让最内层代码插入排序
问题是这个执行效率应该在每台电脑都不一样（CPU设计，不同Excel版本的执行效率，内存速度差异等等）
实际上在我的电脑上面，对随机长整数key排序，最佳数字似乎是7。
[ 本帖最后由 灰袍法师 于 2011-3-31 23:48 编辑 ] |
|
楼主: 灰袍法师
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2011-2-17 21:57
