什么是Java的排序算法

Question

java如何在内部对数据类型进行排序？为什么？如果可以提到具体的算法,那将是很好的

Answer 1

从版本7开始,Oracle的Java实现将Timsort用于大于10个元素的对象数组,对于具有少于该元素数量的数组使用Insertion排序.同样的考虑适用于Arrays.sort()和Collections.sort().在旧版本的Java中,使用Merge sort而不是Timsort.

该语言的其他实现(除了Oracle之外)可能使用不同的排序算法,因为规范并未强制要求.引用Collections' 文件:

此类中包含的多态算法的文档通常包括实现的简要描述.这些描述应被视为实施说明,而不是规范的一部分.只要遵守规范本身,实现者就可以随意替换其他算法.(例如,sort使用的算法不必是mergesort,但它必须是稳定的.)

对于排序数字基元,JDK 7 使用 "双枢轴快速排序".

Answer 2

Collections.sort()使用修改后的mergesort.Arrays.sort()使用quicksort的变体进行基元和mergesort进行Object排序.

对于Java 7,请阅读@SebastianPaaskeTørholm的评论

Answer 3

OK attempting to come up with the canonical list. Basically the contract is that Collections.sort has to be a "stable" sort (i.e. equal elements won't be re-arranged), where Arrays.sort (for native type arrays) can re-arrange them, since they're identical, so it has more freedom to use different (i.e. faster) algorithms. Rationale for wanting stable contract is given here. Also it is presumed that comparing objects (vs. natives) is "much more expensive" (it typically is) so a side-goal for Collections.sort is to minimize number of comparisons, and be stable.

For all versions, Collections.sort initially makes a copy of the list (to an array), modifies that, then copies the sorted elements back into the initial list, to avoid O(n^2) complexity for sorting linked lists. Guess they thought the extra copy wouldn't be too expensive since it's just copying references, not actual values (?).

In JDK 6:

Arrays of native types: tuned quicksort

 * 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).  This algorithm offers n*log(n) performance on many data sets
 * that cause other quicksorts to degrade to quadratic performance.

It was deemed that quadratic "worst case" O(n^2) behavior was not a problem for this modified quicksort.

Quicksort itself was chosen for performance.

List of Objects: modified mergesort

 * The sorting algorithm is a modified mergesort (in which the merge is
 * omitted if the highest element in the low sublist is less than the
 * lowest element in the high sublist).  This algorithm offers guaranteed
 * n log(n) performance. 

"It is a reasonably fast stable sort that guarantees O(n log n) performance and requires O(n) extra space."

It also defaults to an insertion sort for small arrays.

JDK 7:

Arrays of native types: dual-pivot quicksort

 * ...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.

"The new algorithm reduces the average number of swaps by 20%."

There are also certain thresholds where if size is "below x" it will just do a counting sort, insertion sort, or quicksort instead of the "dual pivot quicksort." (depending on what type of primitive is being sorted) /sf/answers/2879046201/

List of Objects: Timsort a kind of hybrid merge/insertion sort.

"It is a stable, adaptive, iterative mergesort that requires far fewer than n log(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts timsort is stable and runs in O(n log n) time (worst case). In the worst case, timsort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space. Contrast this with the current implementation, which always requires extra space for n object references, and beats n log n only on nearly sorted lists."

"On highly ordered data, this code can run up to 25 times as fast as the current implementation."

"1) Guaranteed O(n*log(n)) or less comparisons with a low constant. 2) Exactly n-1 comparisons for presorted (or revsorted) data. 3) Stable sort."

You can revert back to using LegacyMergeSort with an env. setting.

JDK 8:

Arrays of native types: dual-pivot quicksort, with some small modifications over jdk 7 (what?).

List of Objects: Timsort (same)

Parallel sort: ???

JDK 9:

Arrays of native types: dual-pivot quicksort, with at least some small modifications so if data is "mostly ordered" it will just do a modified merge sort on it.

List of Objects: Timsort (same)

并行排序：？？？

JDK 10：

本机类型的数组：双枢轴快速排序，已提出一些修改。

对象列表：Timsort（相同）

并行排序：？？？

这是一个社区维基，随时更新和/或详细说明。