Java Sort函数 [英] Java Sort functions

问题描述

在Java中，collections.sort使用合并排序算法而不是快速排序.但是Arrays.sort使用快速排序. (而且我不确定上述事实，但我在互联网上发现了这一点，例如在

In java the collections.sort used merge sort algorithm instead of quick sort. But Arrays.sort uses quick sort. ( And i am not sure about above fact but i found this on internet like on website such as CodeRanch if they don't use that algoritjm please tell me)

现在我知道两种算法的平均复杂度是相同的.唯一的事实是quicksort最糟糕的是O(n ^ 2)，但这并不常见. 而且我们不关心当今世界的空间，因此合并排序不是就地算法也没关系. 但是我们关心稳定性，所以为什么要对array.sort使用快速排序，因为它不是稳定的算法.是因为它只关注整数，但我不认为这是一个很好的理由.

Now i know average complexity of both algorithm is same. Only fact is quicksort worst is O(n^2) but that's not to common. And we are not concerned with space in today's world so it doesn't matter that merge sort is not in-place algorithm. But we concerned with stability so why we use quick sort for array.sort because its not a stable algorithm. Is it because it only concerned about integer's but i don't think that's a good reason.

推荐答案

可以通过查看相关的 Collections.sort(List<T>) 只需委托给

Your premise can be easily verified by looking at the relevant Javadocs, or even the source code. First, notice that Collections.sort(List<T>) simply delegates to Arrays.sort(Object[]) (source):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

因此，这两种方法将具有相同的行为和运行时间.如文档中所述，实现是 TimSort ，它是一种合并排序和插入排序的混合体.保证稳定.因此，无论您是数组还是集合，对对象进行排序都是相同的.

So these two methods will have the same behavior and runtime. As noted in the documentation, the implementation is TimSort, a merge sort and insertion sort hybrid. It is guaranteed to be stable. So, sorting objects works the same whether you have an array or a collection.

您链接的文章所指的是对原始数组进行排序.关于基本数组需要做出的假设更少，从定义上看，相等的基本体是无法区分的.这意味着无需确保稳定的排序.您会注意到原始排序方法的文档，例如 Arrays.sort(int[]) 没有提及这些排序方法的稳定性，因为这样的细节是没有意义的.稳定性仅在对可以相等但不相同的数据进行排序时才重要.

What the article you link to is referring to is sorting primitive arrays. There are fewer assumptions that need to be made about primitive arrays, notably equal primitives are, by definition, indistinguishable. That means there is no need to ensure a stable sort. You'll notice the documentation for the primitive sort methods, like Arrays.sort(int[]), says nothing about the stability of these sorting methods, because such a detail is meaningless. Stability only matters when sorting data that can be equal but not identical.

这篇关于Java Sort函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！