java - 更高效的排序算法？

Question

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

让我们有两个实现 Comparable 的类，它们的自然排序基于一个 int 值。第一个 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 契约(Contract)不需要这个，需要另一个比较。例如下面的实现也实现了(至少我希望如此)契约(Contract)，但给出了不同的结果(数字排序，但偶数在奇数之前)

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 可能会溢出

Answer 1

排序算法的效率可能取决于很多因素，但需要注意的是，一般来说，如果您基于元素之间的比较进行排序，最快的渐近运行时间是 Ω (n lg n).

然而，构建一个排序比 n lg n 更快的场景是可能的，但这需要使用比仅仅比较更多的信息。这些就是所谓的“线性排序”，它们通过使用元素的值 而不是与另一个元素的比较来排序。这些示例包括桶排序、计数排序和基数排序。

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

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

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

tl;dr:最快可能的基于比较的排序是 Ω(n lg n)。当您可以读取元素的确切值时，排序可能会更快，但线性排序仅适用于某些受限的情况。通常，您应该只使用编程语言的内置排序。