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

xianshu

谢谢了，楼主！

灰袍法师

lee1892 发表于 2013-4-24 15:50
对于快速排序而言，数据量的大小并不会是导致堆栈溢出的主要原因，而是数据是否是精心设计过的。

而所 ...

实际上，一个乱序数组是不太可能造成堆栈溢出的，比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之间，如果你愿意的话，可以反复测试下述代码是否会堆栈溢出，呵呵：
说实在的，我很怀疑坛子里有几个人能设计出这样的顺序，嘿嘿~
=========================================
我就是那个很倒霉的人，在我写我的排序贴时候，就碰到快速排序运行了几十秒（正常只要几秒。。。。。。我还以为死循环了。）
但是。。。仅此一次，以后再也没碰到过了。

《计算机程序设计的艺术》一书，提到如果采用随机分割值，对于随机生成的数据，
出现退化的概率低于 一千万分之一，退化定义为程序的时间复杂度是超过 20*N*logN

所以，随机数据＋随机分割的快速排序，还真的不是想象中的那么“绝对安全”
在完全不能接受任何一次排序出现 耗时20倍 的要求下，单用随机分割的快速排序就不够好了。

当然，对于一般公司数据排序，学校学生排名之类，随机分割的快速排序完全没有任何问题。

mjzxlmg

灰袍法师 发表于 2013-4-25 20:56
实际上，一个乱序数组是不太可能造成堆栈溢出的，比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之 ...

temp_h = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045061, 2354701, 4188161, 9427967, 16764901, 37730309, 67084289, 150958081)



aTemp = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045055, 2354689, 4188161, 9427969)


搞不明白，与数列个数有关系吗？

wyxsg888

太牛了，下载后慢慢消化。

灰袍法师

mjzxlmg 发表于 2013-4-25 21:25
temp_h = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 26 ...

希尔排序的H数组，决定了能够处理多大规模的排序，只看最大数字，然后乘以10就差不多了。
最大数字是900万的话，可以高效处理 9000万规模的排序问题。
因此，我们希望如果有一个高效的H序列，那么这个序列的最大数字最好也比较大，可以应付大规模的排序问题。

上面说的堆栈溢出，是针对快速排序而言，希尔排序不会有这个溢出的问题。

mjzxlmg

灰袍法师 发表于 2013-4-25 22:48
希尔排序的H数组，决定了能够处理多大规模的排序，只看最大数字，然后乘以10就差不多了。
最大数字是900 ...

谢谢指导，努力学习。

lee1892

灰袍法师 发表于 2013-4-25 20:56
实际上，一个乱序数组是不太可能造成堆栈溢出的，比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之 ...

我就是那个很倒霉的人，在我写我的排序贴时候，就碰到快速排序运行了几十秒（正常只要几秒。。。。。。我还以为死循环了。）
但是。。。仅此一次，以后再也没碰到过了。

你完全应该去买彩票了，数10万、百万规模的随机，都能碰到~{:soso_e113:}

endend1980

对于我这样一个VBA新手来说，真是看不懂，但我特想知道能把VBA研究的这么深的会是做什么，是不是每天都要跟VBA打交道，如果只是凭着兴趣去学习，而工作中根本就用不到的话应该学不了这么深吧!

白云人家

i学习，学习了

jiangdong110

晕，落后太多，简直看不懂！