java - 如何对原始数据类型数组调用java内置TimSort

Question

在java中，方法 Arrays.sort 有两个重载(我在这篇文章中感兴趣)，一个用于原始类型，另一个用于引用类型。他们使用不同的排序算法。

如何使用用于引用类型的算法对基本类型进行排序(而不将它们转换为引用类型，也不使用列表)

方法 Arrays.sort(int[]) 使用双枢轴Quicksort .

方法 Arrays.sort(Object[]) 使用TimSort .

如果我有 int[] array = { /* some values here */ }; , 如何使用 TimSort 对其进行排序？(我知道使用 Integer[] array = { /* some values here */ }; 将使用 TimSort，但我不希望这样做，因为使用对象而不是原始数据的开销，并且稍后可能会有一些装箱和拆箱)

或者对原始数据使用 TimSort 效率不高吗？

我找到了 TimSort 的类(class) java.util.TimSort但我无法在我的代码中访问它。

提出这个问题的原因是快速排序的最坏情况是 O(n^2)我曾经遇到过利用这种情况的数组。而 TimSort 的最坏情况为 (n log(n))最好的情况是 O(n)

更新:

我实际上只对 TimSort 的内置方法感兴趣，它不需要是 Arrays.sort 。如果有任何其他内置方法可以使用 TimSort 对原始数据类型进行排序，我们完全欢迎。

Answer 1

java 内置 TimSort 和 ComparableTimSort 不适用于原始数据类型的数组，它只是需要对象数组的排序方法

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen);

虽然DualPivotQuicksort具有基本类型的排序方法，例如:

static void sort(char[] a, int left, int right,
                 char[] work, int workBase, int workLen);
static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen);

更新。虽然这不是关于 Arrays.sort 的原始问题的答案，geeksforgeeks具有 c++/java/python3/c# 的 timsort 实现。 java的方法原型(prototype)是:

public static void timSort(int[] arr, int n);