陣列的排序演算法(JDK1.8)

上一篇文章

陣列

陣列與其他容器的區別有三大方面:效率,型別和保存基本型別的能力，在Java中,陣列是一種效率最高的存盤和隨機訪問物件參考序列的方式，陣列是一個簡單的線序序列，陣列的優點是訪問元素的速度會非常快,但代價是一旦確定了容器的大小,便不可再改變，可能有人會建議使用ArrayList,因為它可以通過創建新的實體然后把舊的實體傳進去,從而達到擴容，就像本人上一篇文章關于StringBuilder資料結構一樣，但我們要知道它們的底層都是基于陣列的，所以說List之前我們會先說到陣列，

無論使用哪種型別的陣列,陣列識別符號其實只是一個參考,指向堆中創建的一個真實物件，這個物件用于保存指向其他物件的參考，可以作為陣列初始化語法一部分隱式地創建此物件,或者用new運算式顯式的創建，不管是基本資料型別的陣列還是參考資料型別的陣列在使用上基本都相同

在C/C++中,你無法回傳一個陣列,只能回傳指向陣列的指標，但是這樣子會造成陣列的生命周期變得困難，容易產生記憶體泄漏問題，而在Java中卻可以直接回傳一個陣列，需要的時候它存在,不需要時垃圾處理器會清理掉它

Arrays

Arrays是專門用來操作陣列的一個工具類，由于我們使用陣列的時候,會經常需要一些對里面元素產生變更的操作，為了省的程式員去重復寫演算法,所以Java里面已經提供好了工具類，在Arrays類中的方法基本上都是靜態的,因此我們不需要去new一個物件，

sort方法

byte型陣列

Arrays.sort方法可以根據陣列的大小和型別從而實作不同的排序，當陣列的型別為byte陣列時的長度小于29的時候,則會使用插入排序

   		for (int i = left, j = i; i < right; j = ++i) {
                byte ai = a[i + 1];
                while (ai < a[j]) {
                    a[j + 1] = a[j];
                    if (j-- == left) {
                        break;
                    }
                }
                a[j + 1] = ai;
            }

大于29的時候則使用計數排序

	int[] count = new int[NUM_BYTE_VALUES];

     for (int i = left - 1; ++i <= right;
         count[a[i] - Byte.MIN_VALUE]++
     );
     for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
         while (count[--i] == 0);
         byte value = (byte) (i + Byte.MIN_VALUE);
         int s = count[i];

         do {
             a[--k] = value;
         } while (--s > 0);
     }

int型陣列

當陣列的型別是int的時候,如果陣列的長度小于47則會使用插入排序

if (leftmost) {
   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小于286,則會使用快速排序

    do {
          if (left >= right) {
              return;
          }
      } while (a[++left] >= a[left - 1]);
      
      for (int k = left; ++left <= right; k = ++left) {
          int a1 = a[k], a2 = a[left];

          if (a1 < a2) {
              a2 = a1; a1 = a[left];
          }
          while (a1 < a[--k]) {
              a[k + 2] = a[k];
          }
          a[++k + 1] = a1;

          while (a2 < a[--k]) {
              a[k + 1] = a[k];
          }
          a[k + 1] = a2;
      }
      int last = a[right];

      while (last < a[--right]) {
          a[right + 1] = a[right];
      }
      a[right + 1] = last;
  }

當長度大于286的時候則會使用歸并排序

        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;

        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { 
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { 
                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 {
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

float型陣列

當陣列是float型的時候就比較復雜了，因為它會分成不同的階段來進行操作

第一階段

將非float的元素移動到末尾,isNaN方法在這里就是判斷一個元素是否為float

 while (left <= right && Float.isNaN(a[right])) {
            --right;
        }
        for (int k = right; --k >= left; ) {
            float ak = a[k];
            if (ak != ak) {
                a[k] = a[right];
                a[right] = ak;
                --right;
            }
        }

public static boolean isNaN(float v) {
        return (v != v);
    }

第二階段

只要是float的元素就會根據規則進行排序

private static void doSort(float[] a, int left, int right,
                               float[] work, int workBase, int workLen) {
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

  int[] run = new int[MAX_RUN_COUNT + 1];
  int count = 0; run[0] = left;

  for (int k = left; k < right; run[count] = k) {
      if (a[k] < a[k + 1]) {
          while (++k <= right && a[k - 1] <= a[k]);
      } else if (a[k] > a[k + 1]) { 
          while (++k <= right && a[k - 1] >= a[k]);
          for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
              float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
          }
      } else {
          for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
              if (--m == 0) {
                  sort(a, left, right, true);
                  return;
              }
          }
      }
      if (++count == MAX_RUN_COUNT) {
          sort(a, left, right, true);
          return;
      }
  }
  if (run[count] == right++) {
      run[++count] = right;
  } else if (count == 1) {
      return;
  }

  byte odd = 0;
  for (int n = 1; (n <<= 1) < count; odd ^= 1);

     float[] b;                
     int ao, bo;            
     int blen = right - left; 
     if (work == null || workLen < blen || workBase + blen > work.length) {
         work = new float[blen];
         workBase = 0;
     }
     if (odd == 0) {
         System.arraycopy(a, left, work, workBase, blen);
         b = a;
         bo = 0;
         a = work;
         ao = workBase - left;
     } else {
         b = work;
         ao = 0;
         bo = workBase - left;
     }

     for (int last; count > 1; count = last) {
         for (int k = (last = 0) + 2; k <= count; k += 2) {
             int hi = run[k], mi = run[k - 1];
             for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                 if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                     b[i + bo] = a[p++ + ao];
                 } else {
                     b[i + bo] = a[q++ + ao];
                 }
             }
             run[++last] = hi;
         }
         if ((count & 1) != 0) {
             for (int i = right, lo = run[count - 1]; --i >= lo;
                 b[i + bo] = a[i + ao]
             );
             run[++last] = right;
         }
         float[] t = a; a = b; b = t;
         int o = ao; ao = bo; bo = o;
     }
 }

當長度小于47的時候則是插入排序

	if (length < INSERTION_SORT_THRESHOLD) {
           if (leftmost) {
               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 {
               do {
                   if (left >= right) {
                       return;
                   }
               } while (a[++left] >= a[left - 1]);
               for (int k = left; ++left <= right; k = ++left) {
                   int a1 = a[k], a2 = a[left];

                   if (a1 < a2) {
                       a2 = a1; a1 = a[left];
                   }
                   while (a1 < a[--k]) {
                       a[k + 2] = a[k];
                   }
                   a[++k + 1] = a1;

                   while (a2 < a[--k]) {
                       a[k + 1] = a[k];
                   }
                   a[k + 1] = a2;
               }
               int last = a[right];

               while (last < a[--right]) {
                   a[right + 1] = a[right];
               }
               a[right + 1] = last;
           }
           return;
       }

階段3:最后的排序

		int hi = right;

        while (left < hi) {
            int middle = (left + hi) >>> 1;
            float middleValue = a[middle];

            if (middleValue < 0.0f) {
                left = middle + 1;
            } else {
                hi = middle;
            }
        }
        while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
            ++left;
        }

        for (int k = left, p = left - 1; ++k <= right; ) {
            float ak = a[k];
            if (ak != 0.0f) {
                break;
            }
            if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
                a[k] = 0.0f;
                a[++p] = -0.0f;
            }
        }

double型別陣列

和float大同小異,這里就省略了~

String型別陣列

由于在Java里String是一個類而并非關鍵字,因此到了底層也就變成了Object型別陣列的排序

public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

這里的排序會用到ComparableTimSort類,關于ComparableTimSort類的介紹翻譯是這樣子的:這是{@link TimSort}的一個近似副本，修改后可與一起使用實作{@link Comparable}的物件陣列，而不是使用顯式比較器，如果您正在使用優化虛擬機，您可能會發現與TimSort和只回傳{@code（（Comparable）first）.compareTo（Second）}的比較器，如果是這種情況，最好洗掉可比較的時間排序到消除代碼重復，

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            int runLen = countRunAndMakeAscending(a, lo, hi);
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;
            }
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

char型別陣列

當char型別陣列長度小于3200的時候就會呼叫dosort方法，和float排序的第二階段很相似

private static void doSort(char[] a, int left, int right,
                               char[] work, int workBase, int workLen) {
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;

        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { 
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { 
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { 
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

當長度大于3200的時候則會使用計數排序

	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
            int[] count = new int[NUM_CHAR_VALUES];

            for (int i = left - 1; ++i <= right;
                count[a[i]]++
            );
            for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
                while (count[--i] == 0);
                char value = (char) i;
                int s = count[i];

                do {
                    a[--k] = value;
                } while (--s > 0);
            }
        }