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

标签 java sorting quicksort timsort

在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 对原始数据类型进行排序,我们完全欢迎。

最佳答案

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

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);

关于java - 如何对原始数据类型数组调用java内置TimSort,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60704997/

相关文章:

java - Quicksort 偶尔不完成?

java - 尝试使用java中的资源和异常

java - Google Cloud KMS java.lang.NoSuchMethodError:com.google.common.base.Preconditions.checkArgument(ZLjava/lang/String; CLjava/lang/Object;)V

C# 根据多个条件对列表进行排序

Python Panda 数据框按月-年排序

c++ - 为什么 'operator>' 需要 const 而 'operator<' 不需要?

c - 快速排序,是否可以输出 N 维数组中的前 m 个排序值,从而比完整的 N 排序更快

java - 通过java/servlet重启tomcat服务

java - 错误 : Exception in thread "main" java. lang.ArrayIndexOutOfBoundsException: 0

c - 永无止境的快速排序