Java 为什么 Arrays.sort 是快速排序算法，为什么不是另一种排序算法？

Why Arrays.sort is quicksort algorithm, why not another sort algorithm?

提问by mr. Vachovsky

Why? Is it faster or more efficient?

为什么？是更快还是更有效？

For systems with one core, we can use quicksort. What should we use on systems with two cores, four cores, or eight cores?

对于只有一个核心的系统，我们可以使用快速排序。我们应该在具有两核、四核或八核的系统上使用什么？

采纳答案by Orbling

Quicksort has O(n log n) average and O(n^2) worst case performance, that is the best "average case" a sort algorithm can be, there are other sort algorithms that have this performance, but quicksort tends to perform better than most.

快速排序具有 O(n log n) 平均和 O(n^2) 最坏情况性能，这是排序算法可以达到的最佳“平均情况”，还有其他排序算法具有这种性能，但快速排序往往表现更好比大多数。

See: http://en.wikipedia.org/wiki/Quicksort

请参阅：http: //en.wikipedia.org/wiki/Quicksort

回答by darioo

Quicksort is fastest on average O(n log(n)), so Sun probably used that as a good metric.

平均而言O(n log(n))，快速排序是最快的，因此 Sun 可能将其用作一个很好的指标。

回答by Paul Tomblin

QuickSort is a common sorting algorithm. It's reasonably fast, except when the data to be sorted is already in inverse order. It's also efficient in space.

QuickSort 是一种常见的排序算法。它相当快，除非要排序的数据已经是相反的顺序。它在空间上也很有效。

回答by Bozho

It is a tunedquicksort. If you are really interested you can read the material mentioned in the documentation.

这是一个经过调整的快速排序。如果您真的有兴趣，可以阅读文档中提到的材料。

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993).

排序算法是一个经过调整的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“设计排序功能”，软件实践和经验，卷。23(11) P. 1249-1265（1993 年 11 月）。

And here is a bit of an explanation - the tuned version gives n*log(n) on many data sets:

这里有一点解释——调整后的版本在许多数据集上给出了 n*log(n)：

This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance

该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降级为二次性能

回答by Michael Borgwardt

Quicksort has the advantage of being completely in place, so it does not require any additional storage, while mergesort (which isactually used by Arrays.sort()for object arrays) and other (all?) guaranteed O(n*log n) algorithm require at least one full copy of the array. For programs that sort very large primitive arrays, that means potentially doubling the overall memory usage.

快速排序具有在适当位置被完全的优点，所以它不需要任何额外的存储，而归并（其是实际使用Arrays.sort()为对象阵列）和其他（所有？）保证为O（n * log n）的算法需要至少一个数组的完整副本。对于对非常大的原始数组进行排序的程序，这意味着可能会使整体内存使用量增加一倍。

回答by iuiz

It depends on what you want to do. The problem with a normal quicksort is, that it can sometimes be in O(n2). So normaly you could use heap sort, but most times quick sort is faster.

这取决于你想做什么。普通快速排序的问题是，它有时可能是 O(n2)。所以通常你可以使用堆排序，但大多数时候快速排序更快。

However the Arrays.sort(...) implementation uses a "tuned tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy [...]" (according to the JavaDoc documentation). This algorithm has has some build in optimizations, that enables it to work on O(n*log(n)), where a normal quicksort would use O(n2).

然而，Arrays.sort(...) 实现使用了“调优的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy [...]”（根据 JavaDoc 文档）。该算法有一些内置优化，使其能够在 O(n*log(n)) 上工作，而普通的快速排序将使用 O(n2)。

Also the Arrays.sort algorithm is tested over and over again and you can be sure that it works and is bugfree (although this can't be guaranteed.)

此外，Arrays.sort 算法经过反复测试，您可以确定它可以正常工作并且没有错误（尽管无法保证）。

iuiz

伊伊兹

回答by Josh Lee

The answer is in Jon L. Bentley and M. Douglas McIlroy's “Engineering a Sort Function”, which the sort function cites.

答案在 Jon L. Bentley 和 M. Douglas McIlroy 的“设计排序函数”中，排序函数引用了这本书。

Shopping around for a better qsort, we found that a qsort written at Berkeley in 1983 would consume quadratic time on arrays that contain a few elements repeated many times—in particular arrays of random zeros and ones. In fact, among a dozen different Unix libraries we found no qsort that could not easily be driven to quadratic behavior; all were derived from the Seventh Edition or from the 1983 Berkeley function.…

Unable to find a good enough qsort, we set out to build a better one. The algorithm should avoid extreme slowdowns on reasonable inputs, and should be fast on ‘random' inputs. It should also be efficient in data space and code space. The sort need not be stable; its specification does not promise to preserve the order of equal elements.

四处寻找更好的 qsort，我们发现 1983 年在 Berkeley 编写的 qsort 会在包含重复多次的几个元素的数组上消耗二次时间——特别是随机零和一的数组。事实上，在十几个不同的 Unix 库中，我们发现没有一个 qsort 不容易被驱动为二次行为；所有这些都源自第七版或 1983 年伯克利函数。...

无法找到足够好的 qsort，我们着手构建一个更好的 qsort。该算法应避免对合理输入的极端减速，并应在“随机”输入上快速。它在数据空间和代码空间中也应该是高效的。排序不需要是稳定的；它的规范不承诺保留相等元素的顺序。

The alternatives were heapsort and mergesort, since Java was created in the early 1990s. Mergesort is less desirable because it requires extra storage space. Heapsort has a better worst-case performance (O(n log n)compared to O(n^2)), but performs more slowly in practice. Thus, if you can control the worst case performance via good heuristics, a tuned quicksort is the way to go.

替代方案是堆排序和归并排序，因为 Java 是在 1990 年代早期创建的。Mergesort 不太理想，因为它需要额外的存储空间。堆排序具有更好的最坏情况性能（O(n log n)与 相比O(n^2)），但在实践中执行速度更慢。因此，如果您可以通过良好的启发式方法控制最坏情况下的性能，那么调整后的快速排序就是要走的路。

Java 7 is switching to Timsort, which was invented in 1993 (implemented in Python in 2002) and has a worst-case performance of O(n log n)and is a stable sort.

Java 7 正在切换到Timsort，它于 1993 年发明（在 2002 年在 Python 中实现）并且具有最坏情况下的性能O(n log n)并且是一种稳定的排序。

回答by Cem

Compared with Quicksort, Mergesort has less number of comparisons but larger number of moving elements.

与 Quicksort 相比，Mergesort 的比较次数较少，但移动元素的数量较多。

In Java, an element comparison is expensive but moving elements is cheap. Therefore, Mergesort is used in the standard Java library for generic sorting

在 Java 中，元素比较很昂贵，但移动元素很便宜。因此，标准 Java 库中使用 Mergesort 进行泛型排序

In C++, copying objects can be expensive while comparing objects often is relatively cheap. Therefore, quicksort is the sorting routine commonly used in C++ libraries.

在 C++ 中，复制对象可能很昂贵，而比较对象通常相对便宜。因此，快速排序是 C++ 库中常用的排序例程。

ref: http://www.cs.txstate.edu/~rp44/cs3358_092/Lectures/qsort.ppt

参考：http: //www.cs.txstate.edu/~rp44/cs3358_092/Lectures/qsort.ppt

回答by pyshcoguy

First of all Arrays.sort doesn't only use quick sort , It uses multiple algorithms java1.6 onwards

首先 Arrays.sort 不仅使用快速排序，它使用 java1.6 以后的多种算法

See below code from Arrays class

请参阅以下来自 Arrays 类的代码

/** * Sorts the specified array into ascending numerical order. * *

/** * 将指定的数组按数字升序排序。* *

Implementation note: 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. * * @param a the array to be sorted */ public static void sort(int[] a) { DualPivotQuicksort.sort(a); }

实施说明：排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的 Dual-Pivot Quicksort *。该算法 * 在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统的（单轴）快速排序实现更快。* * @param a 要排序的数组 */ public static void sort(int[] a) { DualPivotQuicksort.sort(a); }

DualPivotQuicksort.sort(a); // This uses 5 algorithms internally depending upon dataset size 
do checkout the source code of Arrays class.

Before java 1.6 I think it was using three algorithm quick sort for primitive types such as int and mergesort for objects and when quick sort out performs it start heap sort, See here for more details http://cafe.elharo.com/programming/java-programming/why-java-util-arrays-uses-two-sorting-algorithms

在 java 1.6 之前，我认为它对原始类型使用了三种算法快速排序，例如对象的 int 和归并排序，当快速排序执行它时开始堆排序，有关更多详细信息，请参见此处 http://cafe.elharo.com/programming/ java-programming/why-java-util-arrays-uses-two-sorting-algorithms

回答by David McManamon

Arrays.sort()uses multiple sorting algorithms depending on the size and elements in the array.

Arrays.sort()根据数组的大小和元素使用多种排序算法。

• Insertion sort for small arrays
• Merge sort for mostly sorted arrays
• A highly tuned and adaptable dual-pivot & single pivot quicksort for everything else

• 小数组的插入排序
• 大多数排序数组的合并排序
• 高度调整和适应性强的双枢轴和单枢轴快速排序，适用于其他一切

So in practice we see that quicksort is very fast for large arrays of primitives but has some pitfalls when it needs to adapt to partially sorted arrays, when comparisons between objects are slow, for stable sorting and more.

所以在实践中，我们看到快速排序对于大型基元数组非常快，但是当它需要适应部分排序的数组时，当对象之间的比较很慢，稳定排序等等时，它会存在一些缺陷。