algorithm - 插入排序和冒泡排序的比较

Question

我试图找出这两种算法执行所花费的实际时间，我发现的结果与 Internet 上许多地方的信息不一致，这些信息说插入排序更好。然而，我发现冒泡排序执行得更快。我的代码如下。

冒泡排序

for(int j = 0; j < a.length - 1; j++){
    for(int i = 0; i < a.length - 1 - j; i++) {
        count++;
        if(a[i] > a[i+1]){
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    }
}

插入排序

for(int i = 1; i < a.length; i++){  
    for(int j = i - 1; j >= 0; j-- ){   
        if(a[j] > a[i]) {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
    }
}

我是这样计算起止时间的。

long startTime = System.currentTimeMillis();
.....your program....
long endTime   = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(totalTime);

我发现，对于插入排序，运行 10 次的平均时间为 13，对于冒泡排序，它仅为 5。对此有任何解释吗？

Answer 1

您错误地实现了插入排序。应该是插入排序的代码甚至没有对数组进行排序；例如，在输入上尝试

int a[] = {4, 2, 3, 1, 5};

给出输出

[2, 3, 1, 4, 5]

查看演示:http://ideone.com/aFCPft

鉴于代码不起作用，计时数据并不能告诉我们太多信息。