Java Array.sort()源码分析讲解

2024-09-28 12:15:04

阅读起点：

Arrays.sort(nums1);

使用ctrl+左键进入sort()方法

1.Arrays.sort()

关于sort()的方法一共有14个，就目前调用的来看是以下这种最基础的。

 public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

2.DualPivotQuicksort

DualPivotQuicksort即双轴快排，定义了七种原始类型的排序方法。DualPivotQuicksort中使用了private DualPivotQuicksort() {}，防止实例化，实现了sort方法并且定义了以下调整参数:

//归并排序的最大运行次数
private static final int MAX_RUN_COUNT = 67;
//归并排序的最大运行长度
private static final int MAX_RUN_LENGTH = 33;
//如果要排序的数组的长度小于该常数，则优先使用快速排序而不是归并排序
private static final int QUICKSORT_THRESHOLD = 286;
//如果要排序的数组的长度小于此常数，则优先使用插入排序而不是快速排序
private static final int INSERTION_SORT_THRESHOLD = 47;
//如果要排序的字节数组的长度大于该常数，则优先使用计数排序而不是插入排序
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
//如果要排序的 short 或 char 数组的长度大于此常数，则优先使用计数排序而不是快速排序
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

3.DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

该方法定义：

static void sort(int[] a, int left, int right,int[] work, int workBase, int workLen) {}

进入DualPivotQuicksort的sort方法：

 static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }

首先进行了判断，如果要排序的数组小于了之前定义的QUICKSORT_THRESHOLD=286，则优先使用快速排序而不是归并排序，即进入if中的排序sort(a, left, right, true);

4.DualPivotQuicksort.sort(a, left, right, true)

该方法定义：

private static void sort(int[] a, int left, int right, boolean leftmost){}

进入if中的sort(a, left, right, true)方法，我们只截取他的逻辑部分而非排序实现部分。

private static void sort(int[] a, int left, int right, boolean leftmost) {
    int length = right - left + 1;
    // Use insertion sort on tiny arrays
     if (leftmost) {
            /*
             * Traditional (without sentinel) insertion sort,
             * optimized for server VM, is used in case of
             * the leftmost part.
             */
            for (int i = left, j = i; i < right; j = ++i) {
                int ai = a[i + 1];
                while (ai < a[j]) {
                    a[j + 1] = a[j];
                    if (j-- == left) {
                        break;
                    }
                }
                a[j + 1] = ai;
            }
        } else {...........
		........

该方法中，首先判断了数组长度是否小于INSERTION_SORT_THRESHOLD=47，如果小于就使用插入排序，而不是快速排序。leftmost是来选择使用传统的（无标记）插入排序还是成对插入排序，leftmost是表示此部分是否在范围内的最左侧，因为我们最先开始调用的就是基础的sort，没有其他参数，所以就是从头开始排序，leftmost便默认为true，使用传统（无标记）插入排序，如果为false，使用成对插入排序。

5.总结

如果使用最基础的Arrays.sort()，那么排序中会根据数组的长度进行判断，数组越短，length<47,优先选择插入排序，其次length<286,选择快排，其次是归并排序。

到此这篇关于Java Array.sort()源码分析讲解的文章就介绍到这了,更多相关Java Array.sort()内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

深入理解java中Arrays.sort()的用法

Java的Arrays类中有一个sort()方法,该方法是Arrays类的静态方法,在需要对数组进行排序时,非常的好用. 但是sort()的参数有好几种,基本上是大同小异,下面是以int型数组为例的Arrays.sort()的典型用法 import java.util.Arrays; import java.util.Comparator; /** * Arrays.sort()排序 */ public class SortTest { public static void main(Strin
JAVA基于Arrays.sort()实现数组升序和降序

java中对数组进行排序使用Array.sort() 这个默认是升序 @Test public void index4(){ int scores[] = new int[]{1,2,3,89,4}; Arrays.sort(scores); for (int i:scores ) { System.out.println(i); } } 如果想降序怎么办呢? 使用:Arrays.sort(scores,Collections.reverseOrder()); 需要注意的是不能使用基本类型(
Java Arrays.sort()用法详解

Java的Arrays类中有一个sort()方法,该方法是Arrays类的静态方法,在需要对数组进行排序时,非常的好用. 但是sort()的参数有好几种,下面我就为大家一一介绍,这几种形式的用法. 1.Arrays.sort(int[] a) 这种形式是对一个数组的所有元素进行排序,并且是按从小到大的顺序. 举例如下: import java.util.Arrays; public class Main { public static void main(String[] args) { int
java中的arrays.sort()代码详解

Arrays.sort(T[], Comparator < ? super T > c) 方法用于对象数组按用户自定义规则排序. 官方Java文档只是简要描述此方法的作用,并未进行详细的介绍,本文将深入解析此方法. 1. 简单示例 sort方法的使用非常的简单明了,下面的例子中,先定义一个比较Dog大小的Comparator,然后将其实例对象作为参数传给sort方法,通过此示例,你应该能够快速掌握Arrays.sort()的使用方法. import java.util.Arrays; impo
Java的Arrays.sort()方法排序算法实例分析

暂时网上看过很多JDK8中Arrays.sort的底层原理,有些说是插入排序,有些说是归并排序,也有说大于域值用计数排序法,否则就使用插入排序...其实不全对.让我们分析个究竟: // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } 数组一进来,会碰到第一个阀值QUICK
Java使用Arrays.sort()方法实现给对象排序

目录使用Arrays.sort()方法给对象排序麻烦的方法 Arrays.sort()方法浅谈Arrays.sort()原理例子1 基础知识点例子2 双轴快排另外参考了其他博文,算法思路如下使用Arrays.sort()方法给对象排序当我们给一个整型数组或者浮点型之类的数组排序的时候,很简单就可以达到我们排序的目的,无非是排序算法的问题.那么,如果我们现在想根据对象的一个属性值给一个对象数组进行排序呢? 假如我们现在有一个Car类型,Car类中有一个double型的speed属性
Java Array.sort()源码分析讲解

阅读起点: Arrays.sort(nums1); 使用ctrl+左键进入sort()方法 1.Arrays.sort() 关于sort()的方法一共有14个,就目前调用的来看是以下这种最基础的. public static void sort(int[] a) { DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } 2.DualPivotQuicksort DualPivotQuicksort即双轴快排,定义了七种原始类型的排序
Java struts2请求源码分析案例详解

Struts2是Struts社区和WebWork社区的共同成果,我们甚至可以说,Struts2是WebWork的升级版,他采用的正是WebWork的核心,所以,Struts2并不是一个不成熟的产品,相反,构建在WebWork基础之上的Struts2是一个运行稳定.性能优异.设计成熟的WEB框架. 我这里的struts2源码是从官网下载的一个最新的struts-2.3.15.1-src.zip,将其解压即可.里面的目录页文件非常的多,我们只需要定位到struts-2.3.15.1\src\core
Java集合框架源码分析之LinkedHashMap详解

LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM
Java 读写锁源码分析

前言在实际项目中,比如我们有一个共享资源文件,我们程序会会同时并发的去读.写这个共享资源文件,那怎么能保证在高并发场景下安全.高效读写呢?OK,看了下文便知提示:以下是本篇文章正文内容,案例仅供参考一.技术介绍 1.ReentranReadWriteLock是什么? ReadWriteLock提供了readLock和writeLock两种锁的操作机制,一个是读锁,一个是写锁,而它的实现类就是ReentranReadWriteLock 读锁可以在没有写锁的时候被多个线程同时持有,写锁是独占的
Java并发LinkedBlockingQueue源码分析

目录简介常量构造方法 put await isOnSyncQueue signal 简介 LinkedBlockingQueue是一个阻塞的有界队列,底层是通过一个个的Node节点形成的链表实现的,链表队列中的头节点是一个空的Node节点,在多线程下操作时会使用ReentrantLock锁来保证数据的安全性,并使用ReentrantLock下的Condition对象来阻塞以及唤醒线程. 常量 /** * 链表中的节点类 */ static class Node<E> { //节点中的元素
Java BufferedWriter BufferedReader 源码分析

一:BufferedWriter 1.类功能简介: BufferedWriter.缓存字符输出流.他的功能是为传入的底层字符输出流提供缓存功能.同样当使用底层字符输出流向目的地中写入字符或者字符数组时.每写入一次就要打开一次到目的地的连接.这样频繁的访问不断效率底下.也有可能会对存储介质造成一定的破坏.比如当我们向磁盘中不断的写入字节时.夸张一点.将一个非常大单位是G的字节数据写入到磁盘的指定文件中的.没写入一个字节就要打开一次到这个磁盘的通道.这个结果无疑是恐怖的.而当我们使用Buffered
Java并发结合源码分析AQS原理

前言: 如果说J.U.C包下的核心是什么?那我想答案只有一个就是AQS.那么AQS是什么呢?接下来让我们一起揭开AQS的神秘面纱 AQS是什么? AQS是AbstractQueuedSynchronizer的简称.为什么说它是核心呢?是因为它提供了一个基于FIFO的队列和state变量来构建锁和其他同步装置的基础框架.下面是其底层的数据结构. AQS的特点 1.其内使用Node实现FIFO(FirstInFirstOut)队列.可用于构建锁或者其他同步装置的基础框架 2.且利用了一个int类表示
Java并发Timer源码分析

timer在JDK里面,是很早的一个API了.具有延时的,并具有周期性的任务,在newScheduledThreadPool出来之前我们一般会用Timer和TimerTask来做,但是Timer存在一些缺陷,为什么这么说呢? Timer只创建唯一的线程来执行所有Timer任务.如果一个timer任务的执行很耗时,会导致其他TimerTask的时效准确性出问题.例如一个TimerTask每10秒执行一次,而另外一个TimerTask每40ms执行一次,重复出现的任务会在后来的任务完成后快速连续的被
java.util.Collection源码分析与深度理解

写在开头 java.util.Collection 作为Java开发最常用的接口之一,我们经常使用,今天我带大家一起研究一下Collection接口,希望对大家以后的编程以及系统设计能有所帮助,本文所研究的jdk版本为jdk1.8.0_131 明确一下几点: Collection是接口,其继承了Iterable接口 Collection属于单值类型集合,重点子接口List接口和Set接口 Java.util.List接口(有序.不唯一) ArraryList ArrayList 是一个数组队列,
Java集合系列之LinkedHashMap源码分析

这篇文章我们开始分析LinkedHashMap的源码,LinkedHashMap继承了HashMap,也就是说LinkedHashMap是在HashMap的基础上扩展而来的,因此在看LinkedHashMap源码之前,读者有必要先去了解HashMap的源码,可以查看我上一篇文章的介绍<Java集合系列[3]----HashMap源码分析>.只要深入理解了HashMap的实现原理,回过头来再去看LinkedHashMap,HashSet和LinkedHashSet的源码那都是非常简单的.因此,读

Java Array.sort()源码分析讲解

相关推荐

随机推荐