算法的效率

首先要说明一下，我们知道大O表示法把算法的效率分为四个级别：O(1)，O(logN)，O(N)，O(N^2)，分别对应优，良，中，差。
接下来我对三种排序算法做了测试(运行环境：JDK6.0，windows XP命令提示符下执行，AMD 速龙3800+ 2.0GHz，内存512MB DDRII 667两条，双通道。)：

1、先是给一组数组随机赋值，然后把这个数组再复制出两个，分别用三种排序算法为这三组一样的数组进行排序。数组长度为1万，测得排序时间：

冒泡排序消耗时间：0.453

选择排序消耗时间：0.187

插入排序消耗时间：0.062

2、上面测试的结果中差距不是很大吧，那么把这三个数组扩大10倍，长度加到10万，我们看看结果：

冒泡排序消耗时间：49.109

选择排序消耗时间：21.781

插入排序消耗时间：9.016

这下消耗的时间差很多了。

3、测试最理想情况下(数组已经是升序排序了)，各算法的消耗时间(此时各数组长度为1万)：

冒泡排序消耗时间：0.187

选择排序消耗时间：0.218

插入排序消耗时间：0.0

选择排序消耗的时间居然比冒泡排序法多！！插入排序法几乎不需要时间！这是为什么呢？？

原来在冒泡排序法中，最理想的情况下比较的效率为O(N^2)，选择排序法也一样，而插入排序法只需要比较n-1次，也就是说它的效率是O(N)级别的。理想情况下冒泡排序法的交换次数是0。而选择排序法虽然没有交换数据，但每次都对临时变量赋值消耗了时间，所以在最理想情况下，它的效率反而比冒泡低了。插入排序法的情况和选择排序法一样，需要每次比较时进行赋值，但最理想情况下，它的比较次数本来就少，是O(N)级别的，它在比较次数上省下来的资源完全足够用来运行O(N)赋值操作。这样一分析，运行结果就可以解释了。

4、最糟糕情况下(数组已经是降序排序好了的，我们需要把它反过来用升序排序)，各算法的消耗时间(此时各数组长度为1万)：

可以先猜测一下结果：冒泡排序消耗时间最多，选择排序和插入排序消耗时间差不多。
运行一下看看：
冒泡排序消耗时间：0.422

选择排序消耗时间：0.172

插入排序消耗时间：0.172

评论

2 楼 铁耗子 2007-12-17  

寒一个~~~~~

这三种排序都是n^2级别的

按照楼主的说法，所有的比较式排序都是中或以下

1 楼 Godlikeme 2007-12-16  

”我们知道“大O表示法把算法的效率分为四个级别：O(1)，O(logN)，O(N)，O(N^2)。

头一次听说四个级别的划分法。。。