中西排名自定义函数

aoe1981

香川群子 发表于 2014-8-12 11:02
希尔排序的实质是：
以步长为h(1

　　我净给您找麻烦了，我打算自个做一个的，结果有事又放了下……
　　下面是我做的一张图：
　　
　　再研究下您的，毕竟您写的那么认真、专业！

香川群子

aoe1981 发表于 2014-8-12 14:41
　　我净给您找麻烦了，我打算自个做一个的，结果有事又放了下……
　　下面是我做的一张图：
　　

【是因为上一步步长是3，所以步长为1时只需交换2到3行就能交换到位吧……】

理论上：
当前步长h=1，上一次步长h=3时，单个元素到位的最大移动行间隔为 n=(h-1)*h=6

极端例子如：
arr = Array(7, 4, 1, 8, 5, 2, 9, 6, 3)

h=3时排序结果为：
7        4        1
8        5        2
9        6        3

那么对于h=1的序列，移动过程如下：
0                7        4        1        8        5        2        9        6        3
1                4        7                                                        
2                        1        7                                                
3                1        4                                                        
4                                        5        8                                
5                                5        7                                       
6                                                2        8                        
7                                        2        7                                
8                                2        5                                       
9                        2        4                                                
10                                                                6        9        
11                                                        6        8               
12                                                6        7                        
13                                                                        3        9
14                                                                3        8        
15                                                        3        7               
16                                                3        6                        
17                                        3        5                                
18                                3        4                                       

可知最后一个3需要移动6次才能到达3应该在的位置。
(这个可以有数学证明的。)

呵呵。

最少的当然是移动=0次 (已经到位)

因此，关于总的移动次数：
如果原始的m=9个数据随机、平均分布，那么这9个数在h=3排序完成以后，
h=1时的总平均移动次数大约=7.2次。


最少是=0次，最大的就是上述极端例子=18次。
呵呵。

香川群子

对1-9的全部排列组合=362880进行统计计算，结果如下：

移动

移动次数	排列组合数	占比%
0	216	0.06%
1	1728	0.48%
2	7560	2.08%
3	20088	5.54%
4	35640	9.82%
5	47736	13.15%
6	51192	14.11%
7	48168	13.27%
8	40608	11.19%
9	32400	8.93%
10	26352	7.26%
11	19440	5.36%
12	13176	3.63%
13	8856	2.44%
14	5400	1.49%
15	2592	0.71%
16	1080	0.30%
17	432	0.12%
18	216	0.06%
总数	362880

香川群子

希尔排序移动过程的演示

aoe1981

　　备注三句：
　　1.“Donald Shell 最初建议步长选择为n/2并且对步长取半直到步长达到 1。虽然这样取可以比O(n^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。”
　　2.“已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式这项研究也表明‘比较在希尔排序中是最主要的操作，而不是交换。’”
　　3.“比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。”
　　前两句来自维基百科，后一句来自百度百科。

aoe1981

香川群子 发表于 2014-8-12 11:10
然后，下面就是完整的一个希尔排序算法代码例子
（其实同样的希尔排序算法代码，不同的人写法也不同，但基 ...

1. h = (h \ n) * 2 + 1 '按此简化希尔序列计算方法，计算每次的步长h直至h=1

复制代码

　　这样得到的希尔序列只有最后一个是一样的，就是1，中间的数字未必就相同，随着数据量的不同，对吧……
　　又或者，这个希尔序列本就是变化的，但是确有人提出这样的序列：(1, 5, 19, 41, 109,...)

香川群子

aoe1981 发表于 2014-8-14 16:58
　　备注三句：
　　1.“Donald Shell 最初建议步长选择为n/2并且对步长取半直到步长达到 1。虽然这样取可 ...

关于希尔排序的步长参数增量问题，我觉得一般应用没必要那么讲究。

除非是几十万、几百万数量级的排序，速度差异是很小的。

…………
而我发明的算法，可以说是最简单、最容易记忆。

如果要我不复制，而是马上自己写出希尔排序来，我就很容易做到……
根本不需要去背诵、记忆那些据说有神奇效果的增量参数序列。

香川群子

我改写之后的结构、非常简单。

1. Function ShellRecSort(arr)
   
2.     Dim h&, i&, j&, k&, L&, U&
   
3.     L = LBound(arr): U = UBound(arr): h = (U - L + 1)
   
4.     Do
   
5.         h = (h \ 5) * 2 + 1
   
6.         Call InsSort(arr, L, U, h)
   
7.     Loop Until h = 1
   
8.     ShellRecSort = arr
   
9. End Function
   
10. Sub InsSort(trr, L&, U&, Optional h& = 1) '一維
    
11.     Dim i&, j&, t
    
12.     For i = L + h To U
    
13.         t = trr(i)
    
14.         For j = i - h To L Step -h
    
15.             If trr(j) > t Then trr(j + h) = trr(j) Else Exit For
    
16.         Next
    
17.         trr(j + h) = t
    
18.     Next
    
19. End Sub
    

复制代码

aoe1981

香川群子 发表于 2014-8-12 11:10
然后，下面就是完整的一个希尔排序算法代码例子
（其实同样的希尔排序算法代码，不同的人写法也不同，但基 ...

1.     For i = L + h To U
   
2.         t = trr(i)
   
3.         For j = i - h To L Step -h
   

复制代码

　　现在的难点或者巧妙之处在于上述两层循环的循环变量控制上，这个不易理解……
　　我在尝试用自己的思路去写这个控制变量的变化……
　　但有个问题，就是分组数据最后一组不见得就等于步长值，也许会少若干个，此时防止下标越界，是个问题……

香川群子

aoe1981 发表于 2014-8-14 17:41
　　现在的难点或者巧妙之处在于上述两层循环的循环变量控制上，这个不易理解……
　　我在尝试用自己的 ...

【变量t能不能干脆就用trr(i)代替？】

你自己说呢？

如果可以替代，那么为什么要这么做呢？

自己动动脑筋！

…………总之还是你的基础差啊。