更高效的排序算法？ [英] More efficient sort algorithm?

问题描述

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

I'm looking for an algorithm, which could perform better, than Arrays.sort(). I know this will look like a silly question asked million times, but please read on.

让我们有两个实现 Comparable 的类，其自然顺序基于int值。第一个 compareTo 方法如下所示：

Let's have two classes implementing Comparable whose natural ordering is based on an int value. The first compareTo method looks like this:

 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;
        }
    }
}

当我打电话给<$ c时$ c> Collections.sort 在这些条款的实例列表中，它们的表现大致相同。

When I call Collections.sort on list of instances of these clases, they both perform about the same.

我的问题是，是否存在排序算法，这将有益于第一个 compareTo 方法。
在第一个例子中，添加的信息是这样的：

My question is if there is a sorting algorithm, which would benefit of the added information of the first compareTo method. In the first example, the added information is this:

让我们有三个值 ComparableInteger ：

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

现在我们将 c 与<$进行比较c $ c> a ，我们得到2，当我们将 c 与 b 进行比较时，我们从 compareTo 实现很清楚， b 应该在之后，因为 c.compareTo（a）> c.compareTo（b）所以我们知道正确的顺序。现有的 Comparable 合同不需要这个，需要另外一个比较。例如，以下实现也满足（至少我希望）合同，但给出不同的结果（数字排序，但偶数数字在奇数之前）

Now when we compare c to a, we get 2 and when we compare c to b we get 1. From the compareTo implementation it is clear, that the b should go after a, because c.compareTo(a) > c.compareTo(b) so we know the correct order. The existing Comparable contract doesn't require this and needs another comparison. For example following implementation also fulfills(at least I hope) the contract, but gives different result(numbers sorted, but even numbers are before odd numbers)

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



推荐答案

<排序算法的效率有很多可以依赖的东西，但有一点需要注意的是，一般来说，如果你基于元素之间的比较进行排序，那么最快的渐近运行时就是Ω（n lg n）。

然而，可以构建一个可以比<$ c更快地完成排序的场景$ c> n lg n ，但这需要使用更多信息而不仅仅是比较。这些是所谓的线性排序，它使用元素的值进行排序，而不是与另一个元素进行比较。这些示例包括Bucket Sort，Counting Sort和Radix Sort。

It is, however, possible to construct a scenario where sorting can be done faster than n lg n, but this requires using more information than just comparisons. These are the so-called "linear sorts", which sort by using the value of the element rather than a comparison to another element. Examples of these are Bucket Sort, Counting Sort, and Radix Sort.

您提供的第一个比较方法确实提供了额外的信息，这可能会提高分拣速度，但仅限于在有限的条件下。例如，如果您知道没有重复值，并且最小值和最大值之间的每个值仅使用一次，然后你可以执行排序：

The first comparison method you provided does provide extra information, which might enable a faster sort speed, but only under constrained conditions. If, for example, you know that there are no duplicate values, and that every value between the minimum and maximum value is used exactly once, then you could perform a sort by:



1. 执行线性搜索以找到最小值。


2. 将每个元素与最小值进行比较并放置在比较方法给出的索引处。



此方法应采用 2n = O（n）时间。当然，除非对象包含除整数值之外的额外信息，否则您可以直接构造范围 min..max 。此外，如果你可以读取元素的整数值，你可以实现一个正常的桶或对它们进行排序。

This method should take 2n = O(n) time. Of course, unless the objects contain extra information besides the integer value, you could just construct the range min..max directly. Also, if you can read the integer values of the elements, you could just implement a normal bucket or counting sort on them.

tl; dr ：基于比较的最快排序是Ω（n lg n）。当您可以读取元素的确切值时，可以更快地排序，但线性排序仅适用于某些受限情况。一般来说，你应该只使用你的编程语言的内置排序。

tl;dr: The fastest possible comparison based sort is Ω(n lg n). It is possible to sort faster when you can read the exact value of an element, but linear sorts are only work in certain constrained circumstances. In general you should just use your programming language's builtin sort.

这篇关于更高效的排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！