Question

为什么自己写的冒泡排序比java自带的排序方法（快速排序）要快很多？

突然想测试一下两种排序方法的用时差别多大，就写了程序比了一下，按道理快速排序的时间复杂度是nlogn，冒泡是n2，应该快排更快，可是拿了一个数组排序，外面循环一万次，发现冒泡反而比java.util.arrays.sort方法快了很多，重复执行速度会比上次更快一些，比如冒泡用了2362870ns，而java.util.arrays.sort方法居然用了9048636ns，这是为什么呢？
冒泡排序的代码：
public class Arraysort1{
public static void main(String args[]){
int score[]={67,89,87,69,90,100,75,90};
long starttime=System.nanoTime();

for(int i=1;i<=100000;i++){
sort(score);
}
long endtime=System.nanoTime();
System.out.println("Time taken by program:"+(endtime-starttime)+"ns");
}

public static void sort(int temp[]){
for(int i=1;i<temp.length;i++){
for(int j=temp.length-1;j>i;j--){
if(temp[j]<temp[j-1]){
int x=temp[j];
temp[j]=temp[j-1];
temp[j-1]=x;
}
}
}
}
快速排序的代码：
public class Arraysort2{
public static void main(String args[]){
int score[]={67,89,87,69,90,100,75,90};
long starttime=System.nanoTime();

for(int i=1;i<=100000;i++){
java.util.Arrays.sort(score);
}

long endtime=System.nanoTime();
System.out.println("Time taken by program:"+(endtime-starttime)+"ns");
}

Answer 1

弱弱的问一下，你知道快速排序的原理么?如果你知道，那请问你知道快速排序的最坏情斗培虚况也n2么？你所说的nlogn是最好情况，这个和你的标志位元素选择有关，也就是你的数组内容有关。多进行不同类型不同数据的测试，你就会发现问题的答案。个人认为你应该空燃贴出来你的测试代码，否则别人无法中洞了解你的问题所在。

追问

原来是这样，谢谢你，我打算把各种排序方式都试试！！不过，第一遍循环将数组排好序之后，后面再循环排序那1万次已经有顺序的数组，会不会排出来的时间有问题？

追答

每种排序算法对已排好数组的时间复杂度都不相同，如果你感兴趣的话你可以查查《算法导论》这本书。其实我没有理解你为什么要循环排序已排序数组，个人觉得毫无意义。

Answer 2

你把循环提到百万次再试一下

追问

百万次了之后java.util.arrays.sort方法比冒泡快了，这是为什么？循环次数对速度有影响吗？

Answer 3

你的数组多长？

追问

长度10，循环1w次。。。

追答

长度放到10000 测试一下谁快