Java - 为什么我的Bubble排序比我的插入排序更快？

Question

我测量排序完成排序所需的步骤数，无论出于何种原因，气泡排序总是比插入排序快一点，从我读的内容来看，它应该是相反的方式。

不会发布我的完整代码，但我相信这个问题可能与我有我的位置有关。

冒泡排序：

public void sort() 
{ 
    for (out = nElems-1 ; out >= 1 ; out--) 
    { 
     count = count+1; 
     for (in = 0 ; in < out ; in++) 
     { 
      if ((a.get(in)) > (a.get(in+1))) 
      { 
       swap (in, in+1); 
       count = count+2; 
      } 
     } 
    } 
} 

插入排序：

void sort() 
{ 
    Integer temp[] = new Integer[1]; 
    for (out = 1 ; out < nElems ; out++) 
    { 
     count = count+1; 
     temp[0] = a.get(out); 
     in = out; 
     while (in > 0 && a.get(in-1) >= temp[0]) 
     { 
      a.set(in, a.get(in-1)); 
      --in; 
      count = count+2; 
     } 
     a.set(in, temp[0]); 
    } 
} 

，只是举个例子，我整理充满了2000的随机整数3个文本文件的值，从1- 2000年，插入排序的平均值为2,007,677步，而冒泡排序的平均值为2,005,719。

Answer 1

所以，首先，你只测量作业，而不是整体表现。其次，你的插入排序有优化不交换移动的价值，所以你为什么每次添加2到count？你的while循环应该只加1到count，然后当你有a.set(in,temp[0])时，你应该在while循环之外再加1。 （注意 - 为什么temp是一个数组而不仅仅是一个整数？） 现在，如果要测量整体性能，则需要测量比较和分配（最好在两个单独的变量中，因为某些设备/体系结构可能会有这些操作的性能不同）。

编辑：

为了澄清，比较是当你从阵列与操作者比较的两个项目的值等比小于（<）或大于（>）。分配是当您更改数组中的值时（在您的情况下，使用a.set()）。

下面是一些代码的修改（我分裂count成两个变量代表实际的东西，你会想衡量，assignments和comparisons）：

冒泡排序：

public void sort() 
{ 
    for (out = nElems-1 ; out >= 1 ; out--) 
    { 
     for (in = 0 ; in < out ; in++) 
     { 
      comparisons = comparisons+1; 
      if ((a.get(in)) > (a.get(in+1))) 
      { 
       swap (in, in+1); 
       assignments = assignments+2; 
      } 
     } 
    } 
} 

插入排序：

void sort() 
{ 
    int temp = 0; 
    for (out = 1 ; out < nElems ; out++) 
    { 
     count = count+1; 
     temp[0] = a.get(out); 
     in = out; 
     comparisons = comparisons + 1; //You're doing the comparison below at least once 
     while (in > 0 && a.get(in-1) >= temp[0]) 
     { 
      a.set(in, a.get(in-1)); 
      --in; 
      assignments = assignments+1; 
      comparisons = comparisons + 1; 
     } 
     a.set(in, temp[0]); 
     assignments = assignments+1; 
    } 
} 

要考虑的另一件事 - 你在哪里初始化变量count？我在代码中没有看到它，实际上可能是因为您使用的是不同范围内的同一个变量，并且由于您没有将其重置为0，所以无论您选择哪种第二种方法都将其添加到你的第一个号码。