标题翻译
How to call java built-in TimSort on an array of primitive data types
问题
在Java中，方法 Arrays.sort 有两个重载版本（我在这篇文章中感兴趣的），一个用于基本类型，另一个用于引用类型。它们使用不同的排序算法。
如何使用用于引用类型的算法来对基本类型进行排序（既不将它们转换为引用类型，也不使用列表）？
方法 Arrays.sort(int[]) 使用双轴快速排序（Quicksort）。
方法 Arrays.sort(Object[]) 使用TimSort。
如果我有一个 int[] array = { /* 这里有一些值 */ }; ，如何使用TimSort对其进行排序？
（我知道使用 Integer[] array = { /* 这里有一些值 */ }; 会使用TimSort，但我不想这样做，因为使用对象而不是原始数据会有开销，而且可能会稍后进行装箱和拆箱操作）
或者在原始数据上使用TimSort不高效吗？
我找到了一个TimSort的类 java.util.TimSort 但我无法在我的代码中访问它。
提出这个问题的原因是，快速排序的最坏情况是 O(n^2) ，我曾遇到过一个利用了这种情况的数组。而TimSort的最坏情况是 (n log(n)) ，最好情况是 O(n)。
更新：
实际上，我只对有一个内置的TimSort方法感兴趣，它不需要是 Arrays.sort。如果有任何其他内置方法可以使用TimSort对基本数据类型进行排序，那当然可以。
英文翻译
In java, The method Arrays.sort has two overloads (that I am interested in, in this post) one is for primitive types and the other is for reference types. They use different sorting algorithms.
How can I use the algorithm used for reference types to sort primitive types (without converting them to reference types neither using lists)
The method Arrays.sort(int[]) uses Dual-Pivot Quicksort.
The method Arrays.sort(Object[]) uses TimSort.
If I have an int[] array = { /* some values here */ }; , How can I sort it using TimSort?
(I know that using Integer[] array = { /* some values here */ }; will use TimSort but I do not want that because of the overhead of using Objects instead of primitive data and there might be some boxing and unboxing later)
Or is it not efficient to use TimSort on primitive data?
I had found a class for TimSort java.util.TimSort but I couldn't access it in my codes.
The reason for this question is that Quicksort has a worst case of O(n^2) and I had faced an array that exploited that case. While TimSort has a worst case of (n log(n)) and a best case of O(n)
UPDATE:
I am actually interested in just having a built-in method for TimSort, it does not need to be Arrays.sort. If there is any other built-in method to sort primitive data types using TimSort it is totally welcome.
答案1
得分: 0
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的方法原型如下：
public static void timSort(int[] arr, int n);
英文翻译
java built-in TimSort and ComparableTimSort do not work with arrays of primitive data types, it's only sort method expects array of objects
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen);
While DualPivotQuicksort has sort methods for primitive types, like:
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);
Update. Although it's not the answer for original question about Arrays.sort, geeksforgeeks has implementation of timsort for c++/java/python3/c#. Method prototype for java is:
public static void timSort(int[] arr, int n);
专注分享java语言的经验与见解，让所有开发者获益！
评论