寫這篇文章的初衷，是想寫篇Java和算法的實(shí)際應(yīng)用专甩，讓算法不再玄乎钟鸵，而Arrays.sort是很好的切入點(diǎn)，即分析Java的底層原理涤躲，又能學(xué)習(xí)里面的排序算法思想棺耍。希望能給在座各位在工作中或面試中一點(diǎn)幫助！轉(zhuǎn)載請(qǐng)注明出處：Michael孟良
點(diǎn)進(jìn)sort方法：
// 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;
至于大過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ù)列排序。
這是少于閥值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ù)往下走下面的歸并排序：
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
從這里開始，正式進(jìn)入歸并排序（Merge Sort）洞渔！
// 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并不是單一的排序缚态，而是插入排序，快速排序凑阶，歸并排序三種排序的組合猿规，為此我畫了個(gè)流程圖：
算法的選擇：
PS：關(guān)于排序算法的文章宙橱，推薦這兩篇姨俩，個(gè)人覺得寫得挺好，容易入門：
https://mp.weixin.qq.com/s/t0dsJeN397wO41pwBWPeTg
https://www.cnblogs.com/huangbw/p/7398418.html
穩(wěn)定：如果a原本在b前面师郑，而a=b环葵，排序之后a仍然在b的前面；
不穩(wěn)定：如果a原本在b的前面宝冕，而a=b张遭，排序之后a可能會(huì)出現(xiàn)在b的后面；
時(shí)間復(fù)雜度按n越大算法越復(fù)雜來排的話：常數(shù)階O(1)地梨、對(duì)數(shù)階O(logn)菊卷、線性階O(n)、線性對(duì)數(shù)階O(nlogn)宝剖、平方階O(n2)洁闰、立方階O(n3)、……k次方階O(n的k次方)万细、指數(shù)階O(2的n次方)扑眉。
O(nlogn)只代表增長量級(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)回快速排序。
這就是jdk8中Arrays.sort的底層原理品洛，自己在研究和分析中學(xué)到很多树姨，希望能給各位工作中或面試中一些啟發(fā)和幫助！Thanks for watching桥状！
