知識回顧
在上一章節(jié)中，我們介紹了關于Java下的Arrays排序sort算法的數(shù)組長度不超過QUICKSORT_THRESHOLD數(shù)值為286時的算法應用收奔，分別有插入排序，雙軸快排坪哄，單軸快排和結(jié)對插入排序。Java下的Arrays排序sort算法源碼解析（上）翩肌。今天我們來探索另外一種情況。
探索開始
我們先附上下一段的源碼來進行分析：
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// 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;
}
}
這里乍一看會感覺毫無邏輯念祭，這里用的是什么算法功偿，但是我們細細慢慢琢磨冈在，我們可以發(fā)現(xiàn)一定的規(guī)則：
- 首先這個算法是針對于數(shù)組有序性比較好的情況來進行的站玄，它剛開始會從頭到尾遍歷整個數(shù)組，并且如果有序性較好株旷，他會直接掃描通過，速度很快晾剖。
- 這里有一個情況是，如果這里相同的值非常多的時候齿尽，并且是連在一起的，這里設置了一個閾值MAX_RUN_LENGTH數(shù)值為33雕什，當達到這個值，我們就會使用在上一章那里的邏輯進行排序贷岸。
- 最后還有最重要的邏輯，這里會有一個count值可能會讓大家費解偿警，這個值的作用也是設置一個閾值，不過針對的作用是當有序性斷連的次數(shù)達到MAX_RUN_COUNT數(shù)值為67時螟蒸，認為這個數(shù)組無序程度比較高盒使，就不會再繼續(xù)使用這個算法了七嫌，而會使用之前上章介紹的快排，如果有序則使用歸并排序算法
OK诵原，上面那個算法邏輯也比較簡單，沒有什么特殊點绍赛，我們繼續(xù)向下。
// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
int[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new int[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;
}
// Merging
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;
}
int[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
如果到這了腿倚，就說明開始了歸并排序，不過這里的歸并排序我看的并不是很懂敷燎，硬看有點頭大，想了下還是算了箩言，找了個簡單的歸并算法看了下理解了起邏輯。
今日總結(jié)
今天我們補全了關于Arrays的sort方法設下部分分扎，總結(jié)而言為了優(yōu)化數(shù)組的排序速度胧洒，在編寫方法時使用了很多策略來提升性能，閱讀這一段卫漫，讓我更加加深了對于排序算法的理解，這波不虧~~~
