2008-03-20

几种排序算法的性能的统计图

好久没发点有趣的东西了，今天发个来看看。

上个星期raven给了我一组有趣的统计图。跟大家分享下吧～

下面是对几种排序算法的性能的统计图。
x轴是输入数组的大小，从1000到10000；y轴是消耗的时间，单位为ms。
每条统计线所代表的排序算法如底部的图例所示。

每张图代表一种输入类型的状况。
Sorted表示输入是已经排好序的（按照从小到大），
almost-sorted表示大约有20%的元素是不符合顺序的，
reverse表示顺序是颠倒的（按照从大到小排序），
random表示随机的输入。

看不到大图的请点击放大。









可以看到，有好几种排序算法在这个统一坐标上都看不出什么端倪（相对来说太快了……），
而selection sort则很稳定的呈现出平方级的增长。


把坐标轴重新设定一次，再看看状况如何：
（注释：
Shellsort-A采用的是Shell提出的数列，从floor(N/2)开始每次除以2；
Shellsort-B采用的是另一种数列，从floor(N/2)开始每次除以3。
Quicksort-A是采用输入数组在中间位置的元素为分隔点；
Quicksort-B是采用median-of-three为分隔点；
Quicksort-C是采用median-of-five为分隔点；
Quicksort-D是采用输入数组的实际中值为分隔点
）









raven同学或许过段时间会把题目和代码都放出来吧。这家伙最近也是忙。
更新：raven同学发帖了，http://ravenex.javaeye.com/blog/175557。要看源代码的去那里看……

统计实验是在这样的配置上：
Pentium 4 HT 3.20GHz
1GB DDR
JRE 1.6.0 update 3
不知道为什么，无论怎么调节实验次数的参数，出来的结果都会很“抖”。
我在我的老笔记本上也跑过这个实验，就一点都不“抖”，但是比这里的图要慢多了。

P.S. 统计图是用JFreeChart画的。呼，这库我2年前用得快吐血了……源码开放，文档要卖钱，这算盘打得真是响当当的。
评论
RednaxelaFX 2008-03-24
OK，raven同学发了帖了，在这里：http://ravenex.javaeye.com/blog/175557
要看题目和源代码的去那里看嗯
RednaxelaFX 2008-03-22
我这边现在也没有完整的source，在raven同学那边。过一两天吧。等他发了我这边也加个链接过去。
peterwillcn 2008-03-22
提供下源码。。学习。。。谢谢 支持 java 的开源..
BEA 2008-03-21
我一直在学习这个，真的挺好的！
lwwin 2008-03-20
下載了看……
其實很希望有真實的數據，想知道是怎樣統計的數據呢？
這很有趣=3=
发表评论

您还没有登录，请登录后发表评论

RednaxelaFX
搜索本博客
我的相册
6b079187-6cff-3f7a-b005-c6599028c868-thumb
20080627_1
共 38 张
最近加入圈子
存档
最新评论