暫時(shí)網(wǎng)上看過很多JDK8中Arrays.sort的底層原理，有些說是插入排序，有些說是歸并排序，也有說大于域值用計(jì)數(shù)排序法，否則就使用插入排序。。。其實(shí)不全對(duì)。讓我們分析個(gè)究竟：

// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD)
{
       //QUICKSORT_THRESHOLD = 286
        sort(a, left, right, true);
        return;
 }

　　數(shù)組一進(jìn)來，會(huì)碰到第一個(gè)閥值QUICKSORT_THRESHOLD（286），注解上說，小過這個(gè)閥值的進(jìn)入Quicksort （快速排序），其實(shí)并不全是，點(diǎn)進(jìn)去sort(a, left, right, true);方法：

// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD)
{
    if (leftmost)
    {
        ......

　　點(diǎn)進(jìn)去后我們看到第二個(gè)閥值INSERTION_SORT_THRESHOLD（47），如果元素少于47這個(gè)閥值，就用插入排序，往下看確實(shí)如此：

/*
 * 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;

元素少于47用插入排序

　　至于大過INSERTION_SORT_THRESHOLD（47）的，用一種快速排序的方法：

　　1.從數(shù)列中挑出五個(gè)元素，稱為 “基準(zhǔn)”（pivot）；

　　2.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

　　3.遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

快速排序（Quick Sort）

　　這是少于閥值QUICKSORT_THRESHOLD（286）的兩種情況，至于大于286的，它會(huì)進(jìn)入歸并排序（Merge Sort），但在此之前，它有個(gè)小動(dòng)作：

// Check if the array is nearly sorted
    for (int k = left; k < right; run[count] = k) {        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {                if (--m == 0) {
                    sort(a, left, right, true);                    return;
                }
            }
        }        /*
         * The array is not highly structured,
         * use Quicksort instead of merge sort.
         */
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);            return;
        }
    }

　　這里主要作用是看他數(shù)組具不具備結(jié)構(gòu)：實(shí)際邏輯是分組排序，每降序?yàn)橐粋€(gè)組，像1,9,8,7,6,8。9到6是降序，為一個(gè)組，然后把降序的一組排成升序：1,6,7,8,9,8。然后最后的8后面繼續(xù)往后面找。

　　每遇到這樣一個(gè)降序組，++count，當(dāng)count大于MAX_RUN_COUNT（67），被判斷為這個(gè)數(shù)組不具備結(jié)構(gòu)（也就是這數(shù)據(jù)時(shí)而升時(shí)而降），然后送給之前的sort(里面的快速排序)的方法（The array is not highly structured,use Quicksort instead of merge sort.）

　　如果count少于MAX_RUN_COUNT（67）的，說明這個(gè)數(shù)組還有點(diǎn)結(jié)構(gòu)，就繼續(xù)往下走下面的歸并排序。

總結(jié)：

　　從上面分析，Arrays.sort并不是單一的排序，而是插入排序，快速排序，歸并排序三種排序的組合，為此我畫了個(gè)流程圖：

　　O(nlogn)只代表增長(zhǎng)量級(jí)，同一個(gè)量級(jí)前面的常數(shù)也可以不一樣，不同數(shù)量下面的實(shí)際運(yùn)算時(shí)間也可以不一樣。

　　數(shù)量非常小的情況下（就像上面說到的，少于47的），插入排序等可能會(huì)比快速排序更快。 所以數(shù)組少于47的會(huì)進(jìn)入插入排序。

　　快排數(shù)據(jù)越無序越快（加入隨機(jī)化后基本不會(huì)退化），平均常數(shù)最小，不需要額外空間，不穩(wěn)定排序。

　　歸排速度穩(wěn)定，常數(shù)比快排略大，需要額外空間，穩(wěn)定排序。

　　所以大于或等于47或少于286會(huì)進(jìn)入快排，而在大于或等于286后，會(huì)有個(gè)小動(dòng)作：“// Check if the array is nearly sorted”。這里第一個(gè)作用是先梳理一下數(shù)據(jù)方便后續(xù)的歸并排序，第二個(gè)作用就是即便大于286，但在降序組太多的時(shí)候（被判斷為沒有結(jié)構(gòu)的數(shù)據(jù)，The array is not highly structured,use Quicksort instead of merge sort.），要轉(zhuǎn)回快速排序。

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

最新評(píng)論