更高效的排序算法？

Question

我正在寻找一种比Arrays.sort()更好的算法。我知道这看起来像是一个被问了无数次的愚蠢问题，但请继续阅读。

假设有两个实现了Comparable接口的类，它们的自然排序基于一个整数值。第一个compareTo方法如下：

 public int compareTo(ComparableInteger o) {
     return this.value - o.value;        
 }

第二点是这样的：

public int compareTo(ComparableInteger o) {
    if (this.value > o.value) {
        return 1;
    } else {
        if (this.value == o.value) {
            return 0;
        } else {
            return -1;
        }
    }
}

当我对这些类的实例列表调用Collections.sort时，它们的性能大致相同。

我的问题是是否存在一种排序算法，可以从第一个compareTo方法的附加信息中受益。

在第一个示例中，添加的信息是这样的：

让我们有三个ComparableInteger的值：

a == 1
b == 2
c == 3

现在当我们比较c和a时，得到的是2，而当我们比较c和b时，得到的是1。从compareTo的实现可以看出，b应该在a之后，因为c.compareTo(a) > c.compareTo(b)，所以我们知道正确的顺序。现有的Comparable协议不要求这样做，并需要进行另一个比较。例如，以下实现也符合（至少我希望如此）协议，但给出了不同的结果（数字排序，但偶数在奇数之前）。

public int compareTo(ComparableInteger o) {
    if (value % 2 == o.value % 2){
        return value - o.value;
    } else {
        if (value % 2 == 1){
            return 1;
        }else{
            return -1;
        }
    }
}

• 我很清楚第一个例子不可靠，因为int可能会溢出。

- NeplatnyUdaj

---

这是一种微观优化，可能不重要。我相信底层算法是快速排序。我敢打赌你无法测量出性能差异。 - duffymo

有趣的问题。 这让我想起了基数排序。 - Thomas

这只是出于好奇，还是您已经对代码进行了分析，并得出了“sort（...）”方法是热点的结论？Java的集合/数组排序算法是快速排序和归并排序，两者都以O（n * log（n））运行。有更快的排序算法：https://dev59.com/znTYa4cB1Zd3GeqPu3EB - Bart Kiers

这只是一种好奇心。我一直很困惑，是否返回实际差异或只返回0/1/-1都无关紧要。 - NeplatnyUdaj

这很重要。减法可能会溢出，因此它是有问题的。 - tmyklebu

仅供参考，V8引擎（Chrome和Node.js中的Javascript引擎）中内置的排序算法是一种混合快速排序/插入排序，实际上并不是很好。对于标准库排序来说，真正难以超越的是一个简单、直接的堆排序，这才是他们应该使用的。 - Lee Daniel Crocker

Answer 1

有很多因素会影响排序算法的效率，但要注意的一点是，通常情况下，如果你是基于元素之间的比较来排序的话，最快的渐进运行时间是 Ω(n lg n)。

然而，有可能构建出一个情境，在这种情况下，排序可以比 n lg n 更快地完成，但这需要使用比仅使用比较更多的信息。这些被称为“线性排序”，它们通过使用元素的值而不是与另一个元素的比较进行排序。其中的例子包括桶排序、计数排序和基数排序。

你提供的第一种比较方法确实提供了额外的信息，这可能会使排序速度更快，但只在受限条件下才能做到。例如，如果你知道没有重复值，并且每个介于最小值和最大值之间的值都恰好使用了一次，那么可以通过以下方式进行排序：

1. 进行线性搜索以查找最小值。 2. 将每个元素与最小值进行比较，并将其放置在由比较方法给出的索引处。

此方法应该需要 2n = O(n) 的时间。当然，除非对象包含整数值以外的其他信息，否则可以直接构造范围 min..max。此外，如果你可以读取元素的整数值，可以在它们上面实现一个普通的桶排序或计数排序。

简而言之：基于比较的最快排序是 Ω(n lg n)。如果你能读取元素的确切值，那么有可能进行更快的排序，但线性排序只适用于特定的受限环境中。一般情况下，应使用编程语言内置的排序。

- zstewart

---

谢谢！我已经尝试了基数排序算法在整数上的应用，速度大约比“Collections.sort”快2倍。只是我不确定这是因为算法本身还是对象开销的原因。 - NeplatnyUdaj

Answer 2

请注意第一个比较，它并不完全一致。

 public int compareTo(ComparableInteger o) {
     return this.value - o.value; //not always correct
 }

正文：

如Eric Lippert所指出的（该文章是关于C#的，但对Java仍然有效），你的第一个比较是不安全的：

引用： 特别地，对于输入的Int32.MinValue和Int32.MaxValue，它们之间的差值为1。显然最小的整数比最大的整数要小，但这个方法给出了相反的结果！

正文：

正如你所提到的，其他溢出/下溢问题也会出现。

事实上，任何排序算法都需要更多逻辑开销来尝试使用“额外”的信息。这些“额外”的信息会带来一些额外的麻烦和边缘情况。

- ryanyuyu

---

在更多的情况下是不安全的...如果我执行 Integer.MAX_VALUE - 任何负整数，那么它将会溢出。 - NeplatnyUdaj

@NeplatnyUdaj 谢谢。我把措辞改得更加通用了。 - ryanyuyu

但是我已经在原帖中提到过了。我认为这并不会改变问题的很大部分。它可能是 BigInteger... - NeplatnyUdaj

@NeplatnyUdaj 就像我之前提到的那样，“额外”的信息是以处理溢出/下溢问题为代价的。你必须记住数据类型的大小，并进行额外的逻辑来防止每次迭代的溢出/下溢。 - ryanyuyu

Answer 3

我认为第一个compareTo中的额外信息并不像你想象的那样有用：在你的例子中，你只是将对象之间的比较替换为了compareTo结果之间的比较，而这种情况不管使用哪种排序算法都会出现。

- Scott Hunter

---

看起来你是对的。如果 compareTo 很昂贵，那将是有益的。 - NeplatnyUdaj

Answer 4

• 普通算法：3次比较

• 您的算法：2次比较+对先前差异的"缓存"值进行1次比较。(在您的示例中，检查2>1将确定a和b的顺序)

至于复杂度O，它们是相同的，但我感觉您的实现在实践中会稍微慢一些(并且更难实现)。

- Marcin Szymczak

---

我现在明白了。最好创建一个名为 getIntValue 的方法，根据它进行排序，而不是使用 compareTo。我真的没有好好考虑这个问题 :) - NeplatnyUdaj

Answer 5

始终坚持使用核心Java集合功能，例如Arrays.sort()，因为它们已经经过测试，针对到目前为止注意到的所有微妙之处，大多数程序员不太可能考虑到，并且它们还调整了性能。当下一个Java版本发布时，您无需重新测试自己的排序例程。

- Mark Stewart