Coding ManJava 中可用的两种排序方法
1. 概述
在这个快速教程中，我们将比较两个Arrays.sort(Object[]) 和 Arrays.sort(int[]) 排序 操作。
首先，我们将分别描述每种方法。之后，我们将编写性能测试来测量它们的运行时间。
2. Arrays.sort(Object[])
在我们继续之前，重要的是要记住 Arrays.sort() 适用于原始和引用类型数组。
**Arrays.sort(Object[])接受引用类型。
例如，我们有一个Integer对象数组：
Integer[] numbers = {5, 22, 10, 0};
要对数组进行排序，我们可以简单地使用：
Arrays.sort(numbers);
现在，numbers 数组的所有元素都按升序排列：
[0, 5, 10, 22]
*Arrays.sort(Object[])*基于 TimSort 算法，**时间复杂度为 $$O(n\log(n))$$。**简而言之，TimSort 利用了插入排序 和MergeSort 算法。但是，与其他排序算法（如某些 QuickSort 实现）相比，它仍然较慢。
3. Arrays.sort(int[])
另一方面，Arrays.sort(int[])适用于原始int数组。
类似地，我们可以定义一个*int[]*原语数组：
int[] primitives = {5, 22, 10, 0};
*并使用Arrays.sort(int[])*的另一个实现对其进行排序。这一次，接受一组原语：
Arrays.sort(primitives);
此操作的结果与前面的示例没有什么不同。原始数组中的项目如下所示：
[0, 5, 10, 22]
在底层，它使用了 Dual-Pivot Quicksort 算法 。它来自 JDK 10 的内部实现通常比传统的单轴快速排序更快。
**该算法提供$$O(n\log(n))$$平均时间复杂度 。对于许多收藏品来说，这是一个很好的平均排序时间。而且，它具有完全就位的优势，因此不需要任何额外的存储空间。
虽然，在最坏的情况下，它的时间复杂度是$$O(n^2)$$。
4. 时间比较
那么，哪种算法更快，为什么？让我们先做一些理论，然后我们将使用 JMH 进行一些具体的测试。
4.1. 定性分析
由于几个不同的原因， **Arrays.sort(Object[])通常比Arrays.sort(int[])慢。
首先是不同的算法。QuickSort 通常比 Timsort 快。
其次是每种方法如何比较值。
看，**由于Arrays.sort(Object[])需要将一个对象与另一个对象进行比较，它需要调用每个元素的compareTo方法。**至少，除了实际的比较操作之外，这还需要方法查找并将调用压入堆栈。
另一方面，Arrays.sort(int[])可以简单地使用原始关系运算符，例如<和>，它们是单字节码指令。
4.2. JMH 参数
最后，让我们看看哪种排序方法对实际数据运行得更快。为此，我们将使用 JMH （Java Microbenchmark Harness）工具来编写我们的基准测试。
因此，我们将在这里做一个非常简单的基准测试。它并不全面，但会让我们了解如何比较*Arrays.sort(int[])*和 *Arrays.sort(Integer[])*排序方法。
在我们的基准测试类中，我们将使用配置注释：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
public class ArraySortBenchmark {
}
在这里，我们想要测量单个操作的平均时间 ( Mode.AverageTime)并以毫秒为单位显示我们的结果 ( TimeUnit.MILLISECONDS )。此外，使用batchSize参数，我们告诉 JMH 执行 100,000 次迭代以确保我们的结果具有高精度。
4.3. 基准测试
在运行测试之前，我们需要定义我们想要排序的数据容器：
@State(Scope.Thread)
public static class Initialize {
Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737,
1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518,
-1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 };
int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737,
1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518,
-1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167};
}
让我们选择Integer[] 数字和原始元素的int[] 原始数组。@State注释表明在类中声明的变量不会成为运行基准测试的一部分。但是，我们可以在基准方法中使用它们。
现在，我们准备为*Arrays.sort(Integer[])*添加第一个微基准：
@Benchmark
public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) {
Arrays.sort(state.numbers);
return state.numbers;
}
接下来，对于Arrays.sort(int[])：
@Benchmark
public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) {
Arrays.sort(state.primitives);
return state.primitives;
}
4.4. 试验结果
最后，我们运行测试并比较结果：
Benchmark Mode Cnt Score Error Units
benchmarkArraysIntSort avgt 10 1.095 ± 0.022 ms/op
benchmarkArraysIntegerSort avgt 10 3.858 ± 0.060 ms/op
从结果中，我们可以看到**Arrays.sort(int[])方法在我们的测试中比Arrays.sort(Object[])执行得更好，这可能是我们之前确定的原因。
尽管这些数字似乎支持我们的理论，但我们需要使用更多种类的输入进行测试以获得更好的想法。
此外， 请记住，我们在这里提供的数字只是 JMH 基准测试结果——因此我们应该始终在我们自己的系统和运行时范围内进行测试。
4.5. 那么为什么选择 Timsort 呢？
那么，我们或许应该问自己一个问题。如果 QuickSort 更快，为什么不在这两种实现中都使用它呢？
看，QuickSort不稳定，所以我们不能用它来排序Objects。基本上，如果两个 int相等，那么它们的相对顺序保持不变并不重要，因为一个 2 与另一个 2 没有什么不同 。但是对于对象，我们可以按一个属性然后另一个属性排序，从而使起始顺序很重要.