两种排序方法的效率比较-白红宇

两种排序方法的效率比较

阅读量：6603 次

发布时间：2019-06-24

本文共 1919 字，大约阅读时间需要 6 分钟。

前提：笔记本测试，性能一般，测试前开了好多内存杀手。

唯一变量：数组的长度，其余各项均不发生变化。

此测试不具有一般性：数据量太少，实验重复次数不够，没有空白对比试验（~听着怎么像是生物实验了）。如果感兴趣，可以自己做重复实验。

第一种，经典的冒泡排序，代码如下：（A）

long start = System.currentTimeMillis();
int[] num = new int[10000];
for(int i = 0; i < num.length; i++) {
    num[i] = (int)(Math.random() * 10000);
}
//排序
for(int i = 0; i < num.length - 1; i++){
    for (int j = 0; j < num.length - 1 - i; j++) {
        if (num[j] >= num[j + 1]) {
            int k = num[j];
            num[j] = num[j + 1];
            num[j + 1] = k;
        }
    }
}
long end = System.currentTimeMillis();
System.out.println(num[num.length - 1]);
System.out.println(end - start);

第二种，另一种排序方法：（B）

long start = System.currentTimeMillis();
int[] num = new int[1000];
for (int i = 0; i < num.length; i++) {
    num[i] = (int) (Math.random() * 10000);
}
//排序
for (int a = 0; a < num.length; a++) {
    for (int b = 0; b <= a; b++) {    //如果设置b=1开始，效率会不会提高一些呢？
        if (num[a] <= num[b]) {
            int k = num[a];
            num[a] = num[b];
            num[b] = k;
        }
    }
}
long end = System.currentTimeMillis();
System.out.println(num[num.length - 1]);
System.out.println(end - start);

测试方法为：

分别将数组的长度设置为1,000、10,000、100,000三种，本来还想测试1,000,000长度的执行时间，可是时间太长，只好测试这三种了。

测试结果如下：

1,长度为10,00时，两种代码执行时间为：

A：49、31、31、62、31、31、31、31、31、32

B：31、32、32、31、47、31、47、47、31、31

2，长度为10,000时，两种代码的执行时间为：

A：452、452、453、437、452、452、453、452、452、452、437、436

B：218、172、171、188、203、187、187、187、203、187、188、187

3，长度为100,000时，两种代码的执行时间为：

A：23650、23683、27146、28035、23667、28020、23603、28033、28036、28064、26974、27410、23493、23650

B：14573、14570、12168、12217、14602、20593、14695、17004、16975、16209、12215、14556、18161、14573

粗略统计下，分析如下：

1：对于1000组的测试，由于数组过于小了，测试结果并不明显，这也是我列举的数据量少的原因（敲数字太辛苦，懒的再写）；

2：对于10000组的结果分析，得出B组比A组大约快了273毫秒，这个结果有点意思了；

3：对于第三组，差距就明显的多了，B组比A组快了将近10秒！是秒（s），不是毫秒（ms）！这才多大的数据量啊，如果进行100万的测试，估计差距更加大（机器不行，太耗时间，就没测试了）。