Java 排序函数

Question

在 java 中，collections.sort 使用合并排序算法而不是快速排序。但是 Arrays.sort 使用快速排序。（而且我不确定以上事实，但我在互联网上发现了这个，比如在 CodeRanch 等网站上，如果他们不使用该算法，请告诉我）

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

Answer 1

Arrays.sort 会比 Collections.sort 稍微快一些，因为 Collections.sort 在内部调用 Arrays.sort。在处理图元时，稳定性无关紧要，因为可以重新排列具有相同值的图元而没有副作用。 Arrays.sort 提供额外的性能优势。因此，对于原始数组，Arrays.sort 将是首选。

Answer 2

Arrays.sort 并没有真正使用常见的快速排序实现，javadoc 指定：

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

看看位于DualPivotQuicksort的排序算法；正如您在评论中看到的，根据给定的数组使用不同的排序算法。

至于 Collections 排序方法，它在收到的实现上调用 sort，该实现（在我验证的情况下）委托给 Arrays.sort。

Answer 3

Arrays.sort 仅对原始数组使用双枢轴快速排序算法，稳定和不稳定排序算法之间没有区别。这通常被认为是稍微快一点，但它不稳定，所以它只在稳定性无关的情况下使用。

Arrays.sort 在对象数组上，Collections.sort 使用 Timsort，这是一种稳定排序的合并排序变体。

Answer 4

您的前提可以通过查看相关内容轻松验证 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，一种合并排序和插入排序的混合体。它保证稳定。因此，无论您使用的是数组还是集合，排序对象的效果都是一样的。

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

Java 排序函数

Java Sort functions

java

sorting

algorithm

collections