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

Posted on by

閱讀起點：

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()內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：