JDK8 中Arrays.sort() 排序方法详解
作者:ljj234567 时间:2023-01-17 10:38:30
一、引言
在刷算法的时候经常需要对数组
进行排序,第一反应就是直接使用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),使用计数排序
,反之,在小数组的情况下使用插入排序
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 ) ,使用计数排序
,反之,使用双轴快排
。
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);
}
}
来源:https://blog.csdn.net/ka3p06/article/details/130515976
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Android Zxing生成二维码经典案例分享
详解C#如何加密解密RAR文件
![](https://img.aspxhome.com/file/2023/4/113714_0s.png)
C#基于XNA生成随机颜色的方法
IDEA社区版下载安装流程详解(小白篇)
![](https://img.aspxhome.com/file/2023/4/61684_0s.png)
SpringBoot + validation 接口参数校验的思路详解
详解SpringBoot+Lucene案例介绍
Android搜索框通用版
![](https://img.aspxhome.com/file/2023/1/139641_0s.gif)
servlet异步请求的实现
![](https://img.aspxhome.com/file/2023/4/57724_0s.png)
java.lang.String类的使用
android获取手机cpu并判断是单核还是多核
Struts2相关的面试题整理分享
利用Flutter实现“孔雀开屏”的动画效果
![](https://img.aspxhome.com/file/2023/0/138180_0s.gif)
Mybatis resultMap标签继承、复用、嵌套方式
Android去除AlertDialog的按钮栏的分隔线
![](https://img.aspxhome.com/file/2023/9/94289_0s.png)
Android实现app应用多语言切换功能
![](https://img.aspxhome.com/file/2023/0/138520_0s.png)
Mybatis配置之<typeAliases>别名配置元素解析
![](https://img.aspxhome.com/file/2023/7/60447_0s.png)