在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中排序和交换元素的最快方法

回答

相关问题