一、引言
在刷算法的时候经常需要对数组
进行排序,第一反应就是直接使用java.util包下的Arrays.sort()方法直接排序。但在刷算法时会通过时间复杂度
和空间复杂度
对实现的算法进行评价,因此我们需对Arrays.sort()方法有所了解。
本文先行介绍Arrays.sort()中影响排序方式的几个因素。影响因素主要为数组类型
、数组大小
,结合阈值
对排序方式进行选择。
二、Arrays.sort()支持类型
Arrays.sort()重载了很多方法,支持多种数据类型的排序。
三、核心方法DualPivotQuicksort.sort()
进入Arrays.sort()方法的源码,发现内部主要通过DualPivotQuicksort.sort()方法实现排序。该方法通过数组大小、类型结合几个阈值来决定使用哪种排序方式。
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
DualPivotQuicksort类中的几个常量都是比较关键的阈值,决定了该数组的排序使用哪种方法排序。
/**
* 长度小于286的数组,优先使用快排而不是归并
*/
private static final int QUICKSORT_THRESHOLD = 286;
/**
* 长度小于47的数组,优先使用插入而不是快排
*/
private static final int INSERTION_SORT_THRESHOLD = 47;
/**
* 如果是byte数组,长度大于29,计数排序优先于插入排序
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
/**
* 如果是char数组,长度大于3200,计数排序优先于快排
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
1、一般情况的排序方法选择
简单来说,会先计算需要排序的数组长度为n,再根据n的大小及数组元素类型来决定使用什么排序。
根据前两个阈值QUICKSORT_THRESHOLD(286)和INSERTION_SORT_THRESHOLD(47),我们可以看到大多数情况下,排序方法的使用规则是这样的,我们规定需要排序的数组长度为n。
- n < 47,使用插入排序
- 47 <= n < 286,使用快速排序
- n >= 286,使用归并排序
2、byte、char类型的排序
但是,当数组类型为byte或者char时,会使用到其他两个阈值
数组类型为byte
时,查看源码,当数组长度n(right - left) > 29 (COUNTING_SORT_THRESHOLD_FOR_BYTE),使用计数排序
,反之,在小数组的情况下使用插入排序
文章来源:https://www.toymoban.com/news/detail-434461.html
static void sort(byte[] a, int left, int right) {
// Use counting sort on large arrays
if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
int[] count = new int[NUM_BYTE_VALUES];
... } else { // Use insertion sort on small arrays
}
}
数组类型为char
时,查看源码实现,当数组长度n(right - left) < 3200 (COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR ) ,使用计数排序
,反之,使用双轴快排
。文章来源地址https://www.toymoban.com/news/detail-434461.html
static void sort(char[] a, int left, int right,
char[] work, int workBase, int workLen) {
// Use counting sort on large arrays
if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int[] count = new int[NUM_CHAR_VALUES];
...
} else { // Use Dual-Pivot Quicksort on small arrays
doSort(a, left, right, work, workBase, workLen);
}
}
到了这里,关于JDK8 中Arrays.sort() 排序方法解读的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!