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，所以無論您選擇哪種第二種方法都將其添加到你的第一個號碼。