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

2023-05-19 05:05:43 方法 排序 详解

一、引言

在刷算法的时候经常需要对数组进行排序，第一反应就是直接使用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类中的几个常量都是比较关键的阈值，决定了该数组的排序使用哪种方法排序。

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

到此这篇关于jdk8 中Arrays.sort() 排序方法详解的文章就介绍到这了,更多相关JDK8  Arrays.sort() 排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

相关文章