一、引言

在刷算法的時(shí)候經(jīng)常需要對(duì)數(shù)組進(jìn)行排序，第一反應(yīng)就是直接使用java.util包下的Arrays.sort()方法直接排序。但在刷算法時(shí)會(huì)通過時(shí)間復(fù)雜度和空間復(fù)雜度對(duì)實(shí)現(xiàn)的算法進(jìn)行評(píng)價(jià)，因此我們需對(duì)Arrays.sort()方法有所了解。

本文先行介紹Arrays.sort()中影響排序方式的幾個(gè)因素。影響因素主要為數(shù)組類型、數(shù)組大小，結(jié)合閾值對(duì)排序方式進(jìn)行選擇。

二、Arrays.sort()支持類型

Arrays.sort()重載了很多方法，支持多種數(shù)據(jù)類型的排序。

三、核心方法DualPivotQuicksort.sort()

進(jìn)入Arrays.sort()方法的源碼，發(fā)現(xiàn)內(nèi)部主要通過DualPivotQuicksort.sort()方法實(shí)現(xiàn)排序。該方法通過數(shù)組大小、類型結(jié)合幾個(gè)閾值來決定使用哪種排序方式。

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

DualPivotQuicksort類中的幾個(gè)常量都是比較關(guān)鍵的閾值，決定了該數(shù)組的排序使用哪種方法排序。

    /**
     * 長度小于286的數(shù)組，優(yōu)先使用快排而不是歸并
     */
    private static final int QUICKSORT_THRESHOLD = 286;
    /**
     * 長度小于47的數(shù)組，優(yōu)先使用插入而不是快排
     */
    private static final int INSERTION_SORT_THRESHOLD = 47;
    /**
     * 如果是byte數(shù)組，長度大于29，計(jì)數(shù)排序優(yōu)先于插入排序
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
    /**
     * 如果是char數(shù)組，長度大于3200，計(jì)數(shù)排序優(yōu)先于快排
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

1、一般情況的排序方法選擇

簡單來說，會(huì)先計(jì)算需要排序的數(shù)組長度為n，再根據(jù)n的大小及數(shù)組元素類型來決定使用什么排序。

根據(jù)前兩個(gè)閾值QUICKSORT_THRESHOLD（286）和INSERTION_SORT_THRESHOLD（47），我們可以看到大多數(shù)情況下，排序方法的使用規(guī)則是這樣的，我們規(guī)定需要排序的數(shù)組長度為n。

• n < 47，使用插入排序
• 47 <= n < 286，使用快速排序
• n >= 286，使用歸并排序

2、byte、char類型的排序

但是，當(dāng)數(shù)組類型為byte或者char時(shí)，會(huì)使用到其他兩個(gè)閾值

數(shù)組類型為byte時(shí)，查看源碼，當(dāng)數(shù)組長度n（right - left） > 29 (COUNTING_SORT_THRESHOLD_FOR_BYTE)，使用計(jì)數(shù)排序，反之，在小數(shù)組的情況下使用插入排序

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

數(shù)組類型為char時(shí)，查看源碼實(shí)現(xiàn)，當(dāng)數(shù)組長度n（right - left） < 3200 (COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR ) ，使用計(jì)數(shù)排序，反之，使用雙軸快排。

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

到此這篇關(guān)于JDK8 中Arrays.sort() 排序方法詳解的文章就介紹到這了,更多相關(guān)JDK8  Arrays.sort() 排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論