二维数组排序，可与range.sort媲美

Zamyi

灰袍法师 发表于 2012-2-6 20:54
排序测试用几万条数据，都是看不出什么差别的，反正都不会超过0.x秒。

100万就比较明显了

本文主要内容是把二维数组排序转换为一维排序，至于采用快速排序，因为它可以对单独其中某区间进行排序。用希尔自然也是不错的选择。虽然快速排序最讨厌的是溢出堆栈空间，但那样的数据现实毕竟是没有的，多key排序的附件已经改为rnd。

灰袍法师

Zamyi 发表于 2012-2-7 19:00
本文主要内容是把二维数组排序转换为一维排序，至于采用快速排序，因为它可以对单独其中某区间进行排序。 ...

我翻了几本书，都没有说到底简单地 /2 作为分割值有多危险
倒是《计算机程序设计的艺术》一书，有提到如果采用随机分割值，对于随机生成的数据，
出现退化的概率低于 一千万分之一
（退化定义为程序的时间复杂度是超过 20*N*logN，这其实依然是一个可以接受的结果，不算灾难性后果。
这么说来，你原先的想法是正确的，除非人为地构造一个攻击快速排序的数组，否则不用考虑出现“不可接受的退化”。
我自己写了一个VBA验证了一下
我采用随机排序10万次，每次都是对5000个1000到9999的整数排序
最后计算 单次最大耗用时间 跟 平均每次耗用时间 的比例
结果发现
取 /2 作为分割值，最慢的一次排序是平均值的138%
取 随机数 作为分割值，最慢的一次排序是平均值的129%
分别不大。

excelhomeljch

灰袍法师 发表于 2012-2-8 02:04
我翻了几本书，都没有说到底简单地 /2 作为分割值有多危险
倒是《计算机程序设计的艺术》一书，有提到如 ...

个人觉得
     随机分割,是没有一个固定的输入会是"出现极端退化"的数组(或许说是每一次排序运算,那个最坏数组也不同),但固定获取分割值就存在这样一个输入数组,并且无论你运行多少次,还是那个数组.如果说输入是等概率,那么运行次数越多,那么发生最坏情况也应该是越大了.所以说,随机分割,主要是作用是排除人为输入因素.用随机生成数据恐怕是无法比较这个情况.
       初学者的见解,有误,望指正并请见谅.

灰袍法师

excelhomeljch 发表于 2012-2-8 13:06
个人觉得
     随机分割,是没有一个固定的输入会是"出现极端退化"的数组(或许说是每一次排序运算,那个最 ...

我也想过这个问题，不过实验的结果似乎 一直是 /2 分割的退化程度比较大，偶尔才会出现随机分割更退化。
暂时没想到为什么。
当然，快速排序本身最适合的输入就是随机数据，所以也许随机数据真的不适合去考验快速排序。
如果用另一种有规律的数据测试，如 正弦函数，而且周期正好是 n的整除数
就明显是 /2 的退化了，几乎是原有耗时的4倍到10倍不等。
因为正如你说的，简单地 /2 更容易被攻击。
附件是我做实验的文档，完全就是拿Zamyi在顶楼的代码，改了随机分割，再跟原版本对比
待排序的数据越多，退化的百分比越低
所以用比较小的test_size测试会更明显，但是太小的规模耗时太短，很难精确测量，所以。。。。。。最后用的是5000到10000这个范围。
快速排序两个简单版本 - 多次随机测试.rar (45.45 KB, 下载次数: 233)

2012-2-9 21:21 上传

点击文件名下载附件

原附件的计时器计数有错误，已改好重新上传

brdsz

收藏一个，留待慢慢消化

83636368

这个需要仔细研究

赵莲

{:soso_e179:}

赵莲

源码已上传。这类型本来感兴趣的不多。一个Key速度已经相当，两个稍慢，三个更复杂。

没有找到源码呀

Zamyi

赵莲 发表于 2012-5-8 16:10
源码已上传。这类型本来感兴趣的不多。一个Key速度已经相当，两个稍慢，三个更复杂。

没有找到源码呀

附件《多Key二维数组排序.rar》工作表“源码"中.

赵莲

Zamyi 发表于 2012-5-8 16:19
附件《多Key二维数组排序.rar》工作表“源码"中.

看到了，谢谢。

问题是我的求助没写清楚，我不想在2维里排序

因为是是字典 D（X）=D（X）+1
我想根据ITMES的多少次数来排序 得到对应的KEYS

只需要针对ITEMS排序就可以获得一个序列了  然后按照序列去把DEKS，ITEMS  写进新数组去

比如有5个D（X）=D（X）+1 的过程
写进数组 数组行里 左边是写入KEYS对应的值，右边是ITEMS的值
5个过程就5行

我现在是每次把KEYS 和ITEMS 写进2维过渡数组 然后使用排序 再把排序了的过渡数组写入大数组。

过渡数组是多余的了，浪费时间呢