1

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

如何使用用于引用类型的算法对原始类型进行排序（既不使用列表将它们转换为引用类型）

该方法Arrays.sort(int[])使用 Dual-Pivot Quicksort。

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

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

还是在原始数据上使用 TimSort 效率不高？

我为 TimSort java.util.TimSort找到了一个类，但我无法在我的代码中访问它。

这个问题的原因是 Quicksort 有一个最坏的情况，O(n^2)我遇到了一个利用这种情况的数组。虽然 TimSort 有一个最坏的情况(n log(n))和一个最好的情况O(n)

更新：

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

4

1 回答 1

0

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

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

WhileDualPivotQuicksort具有原始类型的排序方法，例如：

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的方法原型是：

public static void timSort(int[] arr, int n);
于 2020-03-16T15:43:37.683 回答