VBA编程技巧 之 排序算法初探

ak47ok

每次回帖、谢谢！辛苦了。

mazeboy

学习一个，。。。。

newexcel3

学习了先，以后用到了再慢慢看。

￡Ulikeme

这部分真是晦涩难懂啊

下标越界

lee1892 发表于 2013-4-20 11:50 堆排序

       按楼主的源代码对已经排好序的序列从新执行一次时，会发现首、尾有一对元素仍然乱序，究其原因是构造堆结构的heapfy函数中do while（上面截图中红色方框中的代码）没有对nChd=nLen（最末端的“二叉”）进行构造堆处理。
      我的办法是将红框中的代码改写为：
    Do While nChd <= nLen
          If nChd + 1 <= nLen Then
                If arr(nChd) < arr(nChd + 1) Then nChd = nChd + 1
          End If
     用两层判断代替一层判断“and”逻辑，是为了避免nChd+1>Ubound(arr)出现“下标越界”的错误。

loquat

报告楼主，我这里运行了3次，都是法师的代码占优，win7 x86 office2007

1. 希尔排序中不同步长序列的对比：
   
2. 随机单精度数据数量：300,000
   
3. Ciura 的 序列：227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1
   
4. 用时 1.992 秒 移动 8,755,650 / N ^ 1.268  比较 8,614,105 / N ^ 1.266
   
5. Tokuda 的 序列：153401, 68178, 30301, 13467, 5985, 2660, 1182, 525, 233, 103, 46, 20, 9, 4, 1
   
6. 用时 2.035 秒 移动 8,766,968 / N ^ 1.268  比较 8,609,923 / N ^ 1.266
   
7. Gonnet & Baeza-Yates 的 序列：136363, 61983, 28174, 12806, 5820, 2645, 1202, 546, 248, 112, 50, 22, 10, 4, 1
   
8. 用时 2.457 秒 移动 11,462,681 / N ^ 1.289 比较 11,312,498 / N ^ 1.288
   
9. 原本的 Sedgewick 双公式 序列：260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1
   
10. 用时 2.055 秒 移动 8,944,443 / N ^ 1.269  比较 8,786,865 / N ^ 1.268
    
11. Sedgewick 单公式 序列：262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1
    
12. 用时 2.164 秒 移动 10,733,532 / N ^ 1.284 比较 10,627,797 / N ^ 1.283
    
13. 基于费波那契数列的 序列：90358, 19001, 4025, 835, 182, 34, 9, 1
    
14. 用时 2.496 秒 移动 13,547,558 / N ^ 1.302 比较 13,435,644 / N ^ 1.301
    
15. 法师改良 前后互质的 Sedgewick 双公式 序列：260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
    
16. 用时 1.953 秒 移动 8,931,327 / N ^ 1.269  比较 8,773,975 / N ^ 1.268

复制代码

1. 希尔排序中不同步长序列的对比：
   
2. 随机单精度数据数量：300,000
   
3. Ciura 的 序列：227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1
   
4. 用时 2.020 秒 移动 8,735,892 / N ^ 1.267  比较 8,593,914 / N ^ 1.266
   
5. Tokuda 的 序列：153401, 68178, 30301, 13467, 5985, 2660, 1182, 525, 233, 103, 46, 20, 9, 4, 1
   
6. 用时 2.047 秒 移动 8,756,526 / N ^ 1.268  比较 8,599,326 / N ^ 1.266
   
7. Gonnet & Baeza-Yates 的 序列：136363, 61983, 28174, 12806, 5820, 2645, 1202, 546, 248, 112, 50, 22, 10, 4, 1
   
8. 用时 2.535 秒 移动 11,507,567 / N ^ 1.289 比较 11,356,964 / N ^ 1.288
   
9. 原本的 Sedgewick 双公式 序列：260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1
   
10. 用时 2.129 秒 移动 8,947,087 / N ^ 1.269  比较 8,789,283 / N ^ 1.268
    
11. Sedgewick 单公式 序列：262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1
    
12. 用时 2.223 秒 移动 10,770,468 / N ^ 1.284 比较 10,664,688 / N ^ 1.283
    
13. 基于费波那契数列的 序列：90358, 19001, 4025, 835, 182, 34, 9, 1
    
14. 用时 2.527 秒 移动 13,443,696 / N ^ 1.302 比较 13,331,041 / N ^ 1.301
    
15. 法师改良 前后互质的 Sedgewick 双公式 序列：260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
    
16. 用时 1.984 秒 移动 8,947,557 / N ^ 1.269  比较 8,789,991 / N ^ 1.268

复制代码

1. 希尔排序中不同步长序列的对比：
   
2. 随机单精度数据数量：300,000
   
3. Ciura 的 序列：227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1
   
4. 用时 2.004 秒 移动 8,743,462 / N ^ 1.267  比较 8,601,707 / N ^ 1.266
   
5. Tokuda 的 序列：153401, 68178, 30301, 13467, 5985, 2660, 1182, 525, 233, 103, 46, 20, 9, 4, 1
   
6. 用时 2.043 秒 移动 8,765,374 / N ^ 1.268  比较 8,608,314 / N ^ 1.266
   
7. Gonnet & Baeza-Yates 的 序列：136363, 61983, 28174, 12806, 5820, 2645, 1202, 546, 248, 112, 50, 22, 10, 4, 1
   
8. 用时 2.543 秒 移动 11,922,617 / N ^ 1.292 比较 11,771,793 / N ^ 1.291
   
9. 原本的 Sedgewick 双公式 序列：260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1
   
10. 用时 2.070 秒 移动 8,947,487 / N ^ 1.269  比较 8,790,500 / N ^ 1.268
    
11. Sedgewick 单公式 序列：262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1
    
12. 用时 2.195 秒 移动 10,812,644 / N ^ 1.284 比较 10,706,802 / N ^ 1.283
    
13. 基于费波那契数列的 序列：90358, 19001, 4025, 835, 182, 34, 9, 1
    
14. 用时 2.551 秒 移动 13,777,762 / N ^ 1.303 比较 13,665,407 / N ^ 1.303
    
15. 法师改良 前后互质的 Sedgewick 双公式 序列：260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
    
16. 用时 1.980 秒 移动 8,939,073 / N ^ 1.269  比较 8,781,776 / N ^ 1.268

复制代码

zwg1987313

多谢楼主分享！

auqblfyv

真的很厉害!!只能看懂一些,要沉下心来看,才看得明白,感谢楼主的分享!

15162039800

谢分享,有个问题请指导

rockey2002

留个脚印,                       /