Java Array.sort()源碼分析講解

更新時間：2022年08月24日 11:51:27 作者：Log1119

Arrays類中有一個sort()方法，該方法是Arrays類的靜態(tài)方法，在需要對數組進行排序時，非常的好用。但是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即雙軸快排，定義了七種原始類型的排序方法。DualPivotQuicksort中使用了private DualPivotQuicksort() {}，防止實例化，實現(xiàn)了sort方法并且定義了以下調整參數:

//歸并排序的最大運行次數
private static final int MAX_RUN_COUNT = 67;
//歸并排序的最大運行長度
private static final int MAX_RUN_LENGTH = 33;
//如果要排序的數組的長度小于該常數，則優(yōu)先使用快速排序而不是歸并排序
private static final int QUICKSORT_THRESHOLD = 286;
//如果要排序的數組的長度小于此常數，則優(yōu)先使用插入排序而不是快速排序
private static final int INSERTION_SORT_THRESHOLD = 47;
//如果要排序的字節(jié)數組的長度大于該常數，則優(yōu)先使用計數排序而不是插入排序
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
//如果要排序的 short 或 char 數組的長度大于此常數，則優(yōu)先使用計數排序而不是快速排序
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，則優(yōu)先使用快速排序而不是歸并排序，即進入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)方法，我們只截取他的邏輯部分而非排序實現(xiàn)部分。

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是來選擇使用傳統(tǒng)的（無標記）插入排序還是成對插入排序，leftmost是表示此部分是否在范圍內的最左側，因為我們最先開始調用的就是基礎的sort，沒有其他參數，所以就是從頭開始排序，leftmost便默認為true，使用傳統(tǒng)（無標記）插入排序，如果為false，使用成對插入排序。

5.總結

如果使用最基礎的Arrays.sort()，那么排序中會根據數組的長度進行判斷，數組越短，length<47,優(yōu)先選擇插入排序，其次length<286,選擇快排，其次是歸并排序。

到此這篇關于Java Array.sort()源碼分析講解的文章就介紹到這了,更多相關Java Array.sort()內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: