在Java中排序和交換元素的最快方法

每個數字都用作下面代碼中用於檢索某些條件值的散列集IntIntHashSet fs和cs中的鍵。然後我檢查條件（如果語句），如果爲true，則交換元素。

int[] list = // given list of positive different ints like [14, 2, 7, 19, 20, 3] 
int l = list.length; 
if (l > 1) { 
    int elI, elJ, fI, fJ, swap; 
    for (int i = 0; i < l; i++) { 
     boolean swapped = false; 
     for (int j = 1; j < l; j++) { 
      elI = list[j - 1]; 
      elJ = list[j]; 
      fI = fs.get(elI); 
      fJ = fs.get(elJ); 
      if (fI > fJ || (fI == fJ && cs.get(elI) > cs.get(elJ))) { 
       swap = list[j]; 
       list[j] = list[j - 1]; 
       list[j - 1] = swap; 
       swapped = true; 
      } 
     } 
     if (!swapped) break; 
    } 
}

它看起來像一個泡泡排序，雖然我不是很肯定。我正在編寫一個耗時的程序，這部分應儘可能優化。

主要問題：使用另一種排序方法如QuickSort會更快嗎？

第二個問題：使用時會更快xor沒有臨時變量的交換方法swap？

[編輯]：我可能有一個包含數千個數字的很長的列表。以上例子很簡單。

來源

2012-09-25 Sophie Sperner

對於部分排序數組和小數據集，冒泡排序將是有效的方法。快速排序僅對大型（巨大）數據集有效。你似乎正在實施冒泡排序，這對小數據集是足夠的。

檢查here爲不同排序算法的效率。

來源

2012-09-25 22:41:58 PermGenError

使用Java，除非基準測試和廣泛分析，否則您不知道。

一些適用於小集合的代碼對於較大的集合可能會變得更糟，反之亦然。取決於何時進行了優化，並具有哪些先決條件。它可以識別XOR可以在機器碼中有效編碼的方式，或者它可以以不同的方式進行編碼。它甚至可能在客戶端和服務器虛擬機之間有所不同。

事實上，Java中用於集合的sort方法已從JDK 6替換爲JDK 7（從IIRC Quicksort轉換爲TimSort，一種來自Python IIRC的混合就地mergesort）。

只是這幾天我一直在爭取的情況下一個在邏輯上只是必須更快，但是任何基準測試顯示，正在執行的相反，這隻能通過JIT優化來解釋不同，由於不同的熱點。效率較低的代碼顯然觸發了更好的優化。

來源

2012-09-25 22:42:34

在Java中排序和交換元素的最快方法

回答

相關問題