为什么我的选择排序比插入排序更快？

Question

选择排序

public class Selection implements Sortable { 
    public void sort(Comparable[] a){ 
     for(int i=0;i<a.length;i++){ 
      int min=i; 
      for(int j=i+1;j<a.length;j++){ 
       if(less(a[j],a[min])){ 
        min = j; 
       } 
      } 
      exch(a,i,min); 
     } 
    } 

    private boolean less(Comparable v,Comparable w){ 
     return v.compareTo(w) <0; 
    } 

    private void exch(Comparable[] a,int i,int j){ 
     Comparable temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
} 

插入排序

public class Insertion implements Sortable{ 
    public void sort(Comparable[] a){ 

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

    } 
} 

这里是我比较时的代码。

public class SortCompare { 

    public static double time(Sortable s,Comparable[] a){ 
     Stopwatch timer = new Stopwatch(); 
     s.sort(a); 
     return timer.elapsedTime(); 
    } 

    public static double timeRandomInput(Sortable s,int N,int T){ 
     double total = 0.0; 
     Double[] a = new Double[N]; 
     for (int t=0;t<T;t++){ 
      for(int i=0;i<a.length;i++){ 
       a[i]= StdRandom.uniform()*10; //get a random number 
      } 
      total+=time(s,a); 
     } 
     return total; 
    } 
} 

主代码

public class Main { 

    public static void main(String[] args) { 
     Selection s = new Selection(); 
     Insertion i = new Insertion(); 
     //ShellSort sh =new ShellSort(); 
     double timeSelection = SortCompare.timeRandomInput(s,2000,100); 
     double timeInsertion = SortCompare.timeRandomInput(i,2000,100); 
     //double timeSh = SortCompare.timeRandomInput(sh,2000,100); 
     System.out.println(timeSelection+" "+timeInsertion); 
    } 
} 

结果出乎我的意料。我已经运行了很多次。我的选择排序总是比插入排序更快。我也多次查看我的代码。我不知道哪里是probelm。

0.43200000000000033 0.9880000000000007 

如果我将数据集更改为10000.选择alomost比Insertion快1倍。

8.276999999999997 17.585000000000008 

我正在看书algorithm 4th。作者说，在平均情况下，插入排序将比选择排序快。

Answer 1

也许是因为执行Insertion Sort没有那么好。它可以用“大量掉期”来书写，就像你做的那样。它通常在教科书中以这种形式出现，但不是在现实生活中 - 一个很好的实现会“移动”元素（不交换它们），然后仅在该循环结束时将添加的元素戳到新打开的位置（而不是使添加的元素“遍历”数组）。这节省了大约一半的动作，并且为了比较每次获得相同的项目（因此在Java中，还有许多边界检查），重复访问数组进行比较。

Answer 2

理论上，插入排序和选择排序的渐近运行时间为O（n^2）。

所以我不确定你为什么期望一个比另一个快。

此外，您正在测试的数据集非常小。如果您使用更大的数据集，我预计运行时间会相对越来越接近。

Answer 3

我在这里犯了一个愚蠢的错误。

只需更改以下代码即可。

public class Insertion implements Sortable{ 
    public void sort(Comparable[] a){ 

     for(int i=1;i<a.length;i++){ 
      for(int j=i;j>0;j--){ 
       if(less(a[j],a[j-1])){ 
        exch(a,j,j-1); 
       } 
       else break;//i forget to add this line... 
      } 
     } 

    } 
}