java - Arrays.sort 实现，具体是做什么的

Question

Arrays.sort 在 Java 中使用什么排序算法？它是否会根据操作系统或输入大小或其他东西动态变化？

Answer 1

您可以从源代码中看到它在 OpenJDK 上的作用。对于原始类型，它对短数组使用插入排序，对长数组使用修改后的快速排序；和对象数组的 tim 排序。

Java 6 数组.sort()

我看不出操作系统会如何影响排序。

Answer 2

查看以下文档Arrays.sort：

实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要远少于 n 次 lg(n) 比较，而当输入数组是随机排序时，它提供传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。临时存储要求从几乎排序的输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等。

该实现在其输入数组中平等地利用升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。它使用了 Peter McIlroy 在 1993 年 1 月的第四届 ACM-SIAM 离散算法研讨会论文集上的“乐观排序和信息理论复杂性”中的技术。

看看源代码：Arrays.sort.

Answer 3

sort方法被重载。

对于 Java 7，请从 这里开始查看不同类型的实现说明，然后再往下看。