JDK8 中Arrays.sort() 排序方法解读

这篇具有很好参考价值的文章主要介绍了JDK8 中Arrays.sort() 排序方法解读。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、引言

在刷算法的时候经常需要对数组进行排序,第一反应就是直接使用java.util包下的Arrays.sort()方法直接排序。但在刷算法时会通过时间复杂度空间复杂度对实现的算法进行评价,因此我们需对Arrays.sort()方法有所了解。

本文先行介绍Arrays.sort()中影响排序方式的几个因素。影响因素主要为数组类型数组大小,结合阈值对排序方式进行选择。

二、Arrays.sort()支持类型

Arrays.sort()重载了很多方法,支持多种数据类型的排序。
JDK8 中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,使用归并排序

JDK8 中Arrays.sort() 排序方法解读

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 ) ,使用计数排序,反之,使用双轴快排文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java创建一个长度为10的数组,利用Arrays.sort(), 为数组元素排序

    程序要求:1)创建一个整型数组,数组的长度为10.                     2)给数组元素赋值,要求乱序。                   3)利用fori循环将数组元素依次输出。                      4)利用Arrays.sort(), 为数组元素排序                   5)采用增加for循环将

    2024年02月08日
    浏览(52)
  • JDK8新特性之方法引用【 ::】

    接下来看看由辉辉所写的关于方法引用的相关操作吧 目录 🥳🥳Welcome Huihui\\\'s Code World ! !🥳🥳 一.是什么 二.为什么要用 三.什么时候用 四.怎么用 常见的引用方式  符号表示: “ ::” 是一种引用运算符,它所在的表达式称为方法引用  1.简化代码 方法引用可以将复杂的代

    2024年02月11日
    浏览(38)
  • 【排序算法详细介绍】桶排序(Bucket Sort)冒泡排序(Bubble Sort)快速排序(Quick Sort)

    今天学习了一些简单的 排序算法 ,其实在我们平时解决问题中经常用到,今天正好一起看了看,记录一下。 如果对你也有帮助,我很开心~ 桶排序是一种排序算法,它将数组划分为一些 有序的桶 ,然后 每个桶再分别排序 。最后,将所有的桶合并起来,得到一个有序的数组。桶排

    2024年01月25日
    浏览(50)
  • 排序算法(stable_sort(), sort())

    sort函数我相信大家都不陌生,今天介绍一个新的排序算法stable_sort stable_sort:稳定排序算法,维持相等元素的原有顺序。 假如我们定义一个字符串数组 这些字符串是按照字典序排列的,我们现在想要words按照单词长度从小到大重排的同时,还希望具有相同长度的元素按照字典

    2024年02月07日
    浏览(54)
  • 【排序算法】堆排序(Heap Sort)

    堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 学习堆排序之前,有必要了解堆!若读者不熟悉堆,建议先了解堆(建议可以通过二叉堆,左倾堆,

    2024年02月01日
    浏览(70)
  • arrays.sort用法详解

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!在编程的世界中,数组(arrays)是一种常见且重要的数据结构,而在Java中,对数组进行排序是经常遇到的需求之一。今天,我们将深入探讨Java中的 Arrays

    2024年02月04日
    浏览(45)
  • 46,排序算法sort

    排序算法sort 常用排序算法 sort 学习目标: 掌握i常用排序算法 算法简介: sort //对容器内元素进行排序 random_shuffle //洗牌,指定范围内的元素随机调整次序 merge //容器元素合并,并存储到另一容器中 reverse //反转指定范围的元素 功能描述: 对容器内元素进行排序 函数原型:

    2024年02月16日
    浏览(41)
  • 【算法】桶排序(Bucket Sort)详解

    桶排序(Bucket Sort)又称箱排序,是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里,再对每个桶分别排好序(可以是递归使用桶排序,也可以是使用其他排序算法将每个桶分别排好序),最后一次将每个桶中排好序的数输出。 桶排序的思想就是把待排序

    2024年01月24日
    浏览(43)
  • Ubuntu之apt-get系列--安装JDK8--方法/教程

    原文网址:Ubuntu之apt-get--安装JDK8--方法/教程_IT利刃出鞘的博客 本文介绍如何在Ubuntu下安装JDK8。 可以通过如下命令判断系统是否已安装jdk: 命令 结果 如上所示,表示还没有安装。 结果: 本处我安装openjdk-8-jdk 可以通过apt安装,命令如下: 命令 结果 如上则表示安装成功,

    2024年02月10日
    浏览(48)
  • JDK8中的新特性(Lambda、函数式接口、方法引用、Stream)

    1.1 关于Java8新特性简介 Java 8 (又称为 JDK 8或JDK1.8) 是 Java 语言开发的一个主要版本。 Java 8 是oracle公司于2014年3月发布,可以看成是自Java 5 以来 最具革命性 的版本。Java 8为Java语言、编译器、类库、开发工具与JVM带来了大量新特性。 特性: 速度更快 代码更少(增加了新的语法

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包