0

在 Java 中，我有一个不同正数的列表。

每个数字都用作哈希集中的键，IntIntHashSet fs并cs在下面的代码中用于检索一些条件值。然后我检查条件（if 语句），如果为真，则交换元素。

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）会更快吗？

第二个问题：在没有临时变量的情况下使用异或交换方法会更快swap吗？

[编辑]：我可能有一个很长的列表，其中包含数千个数字。由于示例，上面的一个很简单。

4

2 回答 2

1

对于部分排序的数组和少量数据，冒泡排序将是有效的方法。快速排序仅对大型（巨大）数据集有效。您似乎正在实施冒泡排序，这对于小型数据集就足够了。

在此处查看不同排序算法的效率。

于 2012-09-25T22:41:58.500 回答
0

使用 Java，除非您对它进行广泛的基准测试和分析，否则您不会知道。

一些适用于小集合的代码可能对大集合效果更差，反之亦然。取决于何时优化，以及有哪些先决条件。它可能会识别 XOR 可以在机器代码中有效编码的方式，或者它可能会以不同的方式对其进行编码。它甚至可能在客户端和服务器 VM 之间有所不同。

事实上，sortJava 中的集合方法已从 JDK 6 替换为 JDK 7（从 IIRC Quicksort 到 TimSort，这是一种来自 Python IIRC 的混合就地合并排序）。

就在这几天，我一直在与逻辑上必须更快的情况作斗争，但任何基准测试都显示相反的结果，这只能通过由于不同的热点而执行不同的 JIT 优化来解释。效率较低的代码显然触发了更好的优化。

于 2012-09-25T22:42:34.920 回答