概述：
JDK提供了概述：
JDK提供了對于數(shù)組排序的庫函數(shù)逞带，java.util.Arrays類中的一些列重載的sort的方法為給定數(shù)組進行排序劫拗，以下是各個重載方法簽名：
void sort (char[])
void sort (char[], int, int)
void sort (byte[])
void sort (byte[], int, int)
void sort (T[], Comparator)
void sort (short[], int, int)
void sort (short)
void sort (double[], int, int)
void sort (Object[])
void sort (Object[], int, int)
void sort (T[], int, int, Comparator)
void sort (double[])
void sort (float[], int, int)
void sort (float[])
void sort (int[], int, int)
void sort (long[])
void sort (long[], int, int)
void sort (long[])
對于這些sort方法，我們可以從不同的角度分類：
根據(jù)第一個參數(shù)的類型他匪，可以將這些方法分為3類：基本數(shù)據(jù)類型數(shù)組的數(shù)值排序方法，提供了對于byte衣吠，short萍肆，int亲铡，long，char保屯，float切蟋，double這些基本數(shù)據(jù)類型的數(shù)組的排序方法；自定義類的對象數(shù)組排序方法歧杏。提供了對于任意類類型個數(shù)組的排序方法镰惦，這些方法的輸入?yún)?shù)為Object數(shù)組；泛型方法提供了泛型對象數(shù)組的排序?qū)崿F(xiàn)犬绒。 根據(jù)參數(shù)的個數(shù)旺入，可以將這些方法分為3類：包含1個參數(shù)的方法對整個數(shù)組排序，包含3個參數(shù)的方法對數(shù)組的一部分進行排序凯力，后兩個參數(shù)確定了數(shù)組中要排序元素的范圍茵瘾；泛型方法中包含比較元素大小時使用的比較器類。 根據(jù)實現(xiàn)的原理咐鹤，可以將這些方法分為2類：數(shù)據(jù)數(shù)組排序方法采用一種結(jié)合了歸并排序拗秘、插入排序、改進后的快速排序算法來實現(xiàn)祈惶，這些方法提供了以上7種基本數(shù)據(jù)類型的數(shù)組的排序雕旨；對象數(shù)組排序方法則。捧请。凡涩。。疹蛉。活箕。。可款。育韩。，這些方法提供了對象數(shù)組和泛型數(shù)組的排序算法的實現(xiàn)筑舅。
下文的討論基于最后一種分類角度進行座慰。本文首先來分析數(shù)據(jù)數(shù)組排序方法的實現(xiàn)。
數(shù)據(jù)數(shù)組排序方法：
·代碼：
據(jù)數(shù)組排序方法提供了byte翠拣，short版仔，int，long，char蛮粮，float益缎，double 這7種基本數(shù)據(jù)類型的數(shù)組的排序?qū)崿F(xiàn)。下面以int數(shù)組排序方法的實現(xiàn)為例然想，分析程序排序機理莺奔。
以下為int數(shù)組對應(yīng)的sort方法的代碼實現(xiàn)：
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
方法實現(xiàn)很簡單，直接調(diào)用DualPivotQuicksort類中的sort方法實現(xiàn)排序变泄，該方法代碼如下：
/**
* Sorts the specified range of the array using the given
* workspace array slice if possible for merging
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param work a workspace array (slice)
* @param workBase origin of usable space in work array
* @param workLen usable size of work array
*/
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;
}
/*
* 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;
}
}
// 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é)合起來，實現(xiàn)數(shù)組的排序妨蛹，下文中屏富，筆者首先介紹歸并排序的改進，然后介紹快速排序的改進算法蛙卤。
·對于歸并排序的改進：
以上方法對給定數(shù)組的指定區(qū)間內(nèi)的數(shù)據(jù)進行排序狠半，同時允許調(diào)用者提供用于歸并排序的輔助空間。實現(xiàn)思路為：首先檢查數(shù)組的大小颤难，如果數(shù)組比較小辕坝，則直接調(diào)用改進后的快速排序完成排序(這個改進的快速排序我們在后面介紹)吃既，如果數(shù)組較大皇钞，則評估數(shù)組的無序程度嘿架，如果這個數(shù)組幾乎是無序的，那么同樣調(diào)用改進后的快速排序算法排序栅屏；如果數(shù)組基本有序捂敌，那么采用歸并排序算法對數(shù)組進行排序。
根據(jù)這樣的思路既琴，整個代碼實現(xiàn)可以分為3個部分：
·第一部分
代碼的 15-18 行為第一部分占婉，這一部分檢查了數(shù)組的大小，如果數(shù)組大小小于QUICKSORT_THRESHOLD的值甫恩，則程序認為數(shù)組很小逆济，可以直接調(diào)用改進快排實現(xiàn)排序。常量QUICKSORT_THRESHOLD的值程序定義為286磺箕。
· 第二部分：
代碼的 20-61行為第二部分奖慌，該部分對于數(shù)組的無序程度進行了評估。評估的基于這樣的思路：對于任意的數(shù)組松靡，我們總是可以將其分割成若干個遞增或遞減的子數(shù)組(或者說：拆分成若干個“單調(diào)”的子數(shù)組)简僧，例如：序列 {9, 5, 2, 7, 8, 3, 4} 可以拆分為3個單調(diào)子數(shù)組：{9， 5雕欺， 2}岛马、{7棉姐， 8}、{3啦逆， 4}伞矩， 其中每一個子數(shù)組都是單調(diào)的，不是遞增夏志，就是遞減乃坤。
程序定義run數(shù)組來存儲每一個子數(shù)組的開始下標，該部分的for循環(huán)體對于遞增沟蔑、遞減湿诊、相等的子序列進行了處理，29瘦材、30行的if分句判定了遞增子序列枫吧；31-35行的else if分句處理的遞減序列，同時將遞減序列轉(zhuǎn)化為遞增序列宇色；36-43的else分句處理了相等的序列。下圖描述了run數(shù)組和待排序a數(shù)組的關(guān)系：
需要說明的是颁湖，30行和32行的while循環(huán)的第2個條件都包含了等于宣蠕，因此，只有前面的 if 和 else if的情況都不成立時甥捺，后面的else分句才會執(zhí)行抢蚀，例如：序列{1， 2镰禾， 3皿曲， 3， 3吴侦， 3}屋休，以及{3， 2备韧， 1劫樟， 1， 1}劃分后僅為1個子序列织堂，就是它本身叠艳；而序列{1， 2易阳， 3附较， 2， 2潦俺， 2}則會被劃分成2個子序列：{1拒课， 2徐勃， 3} 和 {2， 2捕发， 2}疏旨。
45-52行給出了評估數(shù)組無序程度的指標，即考察劃分出的子序列的個數(shù)扎酷，即run數(shù)組的大小檐涝，如果run數(shù)組元素個數(shù)大于常量 MAX_RUN_COUNT， 那么認為整個數(shù)組基本上是無序的法挨，此時調(diào)用改進的快排算法排序谁榜，后面的代碼不再執(zhí)行；否則凡纳，程序認為整個數(shù)組基本上是有序的窃植，繼續(xù)執(zhí)行下面的代碼，利用歸并排序算法完成排序荐糜。常量程序MAX_RUN_COUNT定義其值為67巷怜。
55-58行給run數(shù)組的末尾添加了一個“哨兵”元素，這個元素的值為right+1暴氏，代表一個空的子序列延塑。這里又分為兩種情況：如果原數(shù)組在劃分后最后一個元素獨自為一個子序列，那么在27-43行的循環(huán)執(zhí)行完畢后答渔，run數(shù)組的最后一個元素的值為right关带，此時須有再添加一個代表空序列的哨兵元素；如果劃分后沼撕，原數(shù)組中的最后一個元素并不是獨自為一個子序列宋雏，那么27-43行的循環(huán)執(zhí)行完畢后，run數(shù)組的最后一個元素的值就是right+1务豺，此時run數(shù)組的最后一個元素已經(jīng)是哨兵磨总，就不需要再添加了。
程序執(zhí)行到這里笼沥，意味著程序認為數(shù)組基本上是有序的舍败，采用歸并排序算法進行排序，這個哨兵元素的作用在第三部分的代碼中會有體現(xiàn)敬拓，這里略過邻薯。
59-61行給出了另一種特殊情況，即整個數(shù)組劃分后就只有1個單調(diào)子序列乘凸，那么說明數(shù)組本身就是有序的厕诡，不需要再執(zhí)行其他操作，程序結(jié)束营勤。
最后灵嫌，筆者感到困惑的地方是：36-42行關(guān)于相等序列的處理壹罚，程序判定，如果相等序列的長度不小于MAX_RUN_LENGTH寿羞，那么就直接調(diào)用改進快排來處理猖凛。這里的常量MAX_RUN_LENGTH的值是33，是一個很小的數(shù)字绪穆，筆者暫時不了解此設(shè)定的用意!
· 第三部分：
63-109行為本程序的第三部分辨泳，該部分程序?qū)澐趾玫臄?shù)據(jù)進行了二路歸并排序。排序過程中用到了隨參數(shù)傳入的輔助空間work玖院。
63-85行是一個初始化的操作菠红，該操作的意義我們在后面說明，首先看87-108行的代碼难菌，這里是歸并排序的主體试溯，循環(huán)的每一輪迭代都將數(shù)組a中的兩個相鄰的單調(diào)子序列“歸并”為一個新的單調(diào)子序列，存儲在數(shù)組b中郊酒。89行開始的內(nèi)層的for循環(huán)成對地歸并數(shù)組a中的單調(diào)子序列遇绞，如下圖：
循環(huán)中的每輪迭代將兩個相鄰的單調(diào)子序列進行歸并，第一個子序列的范圍是run[k-2] - run[i-1], 第二個子序列的范圍是run[k-1] - run[k]燎窘，內(nèi)層循環(huán)每次迭代都將k增加2摹闽。同時last變量記錄了歸并得到的新的子序列的個數(shù)，同時更新run數(shù)組的內(nèi)容荠耽。
但是，這里有一個問題比藻，如果a數(shù)組中的子序列個數(shù)是奇數(shù)铝量，那么最后一個子序列就無法進行配對、歸并操作银亲，此時慢叨，直接將這個子序列復制到b中。 代碼是100-105行完成了這個工作务蝠。
顯然拍谐，每輪迭代以后，子序列的數(shù)目都會減少馏段，因此轩拨，反復地進行迭代歸并后，最終會使得整個數(shù)組只包含1個單調(diào)遞增的子序列院喜，此時整個數(shù)組排序完成亡蓉。因此，每輪迭代后喷舀，交換a砍濒、b指針淋肾，繼續(xù)執(zhí)行下一輪迭代時，同樣對a數(shù)組進行歸并爸邢，存儲在b數(shù)組中樊卓。就這樣，利用a和b代表的存儲空間仿佛地進行歸并杠河，就可以完成數(shù)組的排序碌尔。106-107行的代碼完成了交換a和b指針的工作。
這里也就解釋了67-85行代碼的意義感猛，初始情況下七扰，a和b指針一定1個指向原數(shù)組，另一個指向輔助空間陪白。下面的if語句則根據(jù)需要的迭代次數(shù)對a和b指針的指向進行指定颈走，確保在迭代歸并結(jié)束以后，排好序的數(shù)組依舊在調(diào)用函數(shù)之前的存儲空間內(nèi)咱士。這里的代碼還檢查了輔助空間的大小是否足夠，如果不夠锐膜，則重新申請內(nèi)存弛房。
最后文捶，對于89行的循環(huán)還有一個問題荷逞，當處理a數(shù)組的最后一對單調(diào)子序列的歸并操作時，此時坠敷，hi的值已經(jīng)超出了run數(shù)組的大小，即k值已經(jīng)越界弄抬，為了避免這種情況的發(fā)生，我們在run數(shù)組的末尾添加了一個“哨兵”元素依啰，這樣就保證了在循環(huán)過程中不會發(fā)生數(shù)組越界的異常。代碼的55-61行闷旧、98行、以及104行完成了添加哨兵元素的工作。
以上是本函數(shù)對于歸并排序的改進算法里初。
·對于快速排序的改進：
以上的代碼的16、39、50行調(diào)用了DualPivotQuicksort類中的另一個排序方法哑诊，該方法的實現(xiàn)機理是基于對于傳統(tǒng)快速排序的改進竞阐，該方法在數(shù)據(jù)無序程度較嚴重時被調(diào)用颗搂，代碼如下：
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param leftmost indicates if this part is the leftmost in the range
*/
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
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 {
/*
* Skip the longest ascending sequence.
*/
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
/*
* Every element from adjoining part plays the role
* of sentinel, therefore this allows us to avoid the
* left range check on each iteration. Moreover, we use
* the more optimized algorithm, so called pair insertion
* sort, which is faster (in the context of Quicksort)
* than traditional implementation of insertion sort.
*/
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;
}
// Inexpensive approximation of length / 7
int seventh = (length >> 3) + (length >> 6) + 1;
/*
* Sort five evenly spaced elements around (and including) the
* center element in the range. These elements will be used for
* pivot selection as described below. The choice for spacing
* these elements was empirically determined to work well on
* a wide variety of inputs.
*/
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
// Sort these elements using insertion sort
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
}
}
}
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
/*
* Use the second and fourth of the five sorted elements as pivots.
* These values are inexpensive approximations of the first and
* second terciles of the array. Note that pivot1 <= pivot2.
*/
int pivot1 = a[e2];
int pivot2 = a[e4];
/*
* The first and the last elements to be sorted are moved to the
* locations formerly occupied by the pivots. When partitioning
* is complete, the pivots are swapped back into their final
* positions, and excluded from subsequent sorting.
*/
a[e2] = a[left];
a[e4] = a[right];
/*
* Skip elements, which are less or greater than pivot values.
*/
while (a[++less] < pivot1);
while (a[--great] > pivot2);
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of ?-part.
*/
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
a[k] = a[less];
/*
* Here and below we use "a[i] = b; i++;" instead
* of "a[i++] = b;" due to performance issue.
*/
a[less] = ak;
++less;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] < pivot1) { // a[great] <= pivot2
a[k] = a[less];
a[less] = a[great];
++less;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
/*
* Here and below we use "a[i] = b; i--;" instead
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
--great;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
/*
* If center part is too large (comprises > 4/7 of the array),
* swap internal pivot values to ends.
*/
if (less < e1 && e5 < great) {
/*
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
++less;
}
while (a[great] == pivot2) {
--great;
}
/*
* Partitioning:
*
* left part center part right part
* +----------------------------------------------------------+
* | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
* +----------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (*, less) == pivot1
* pivot1 < all in [less, k) < pivot2
* all in (great, *) == pivot2
*
* Pointer k is the first index of ?-part.
*/
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak == pivot1) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else if (ak == pivot2) { // Move a[k] to right part
while (a[great] == pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] == pivot1) { // a[great] < pivot2
a[k] = a[less];
/*
* Even though a[great] equals to pivot1, the
* assignment a[less] = pivot1 may be incorrect,
* if a[great] and pivot1 are floating-point zeros
* of different signs. Therefore in float and
* double sorting methods we have to use more
* accurate assignment a[less] = a[great].
*/
a[less] = pivot1;
++less;
} else { // pivot1 < a[great] < pivot2
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
}
// Sort center part recursively
sort(a, less, great, false);
} else { // Partitioning with one pivot
/*
* Use the third of the five sorted elements as pivot.
* This value is inexpensive approximation of the median.
*/
int pivot = a[e3];
/*
* Partitioning degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +-------------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +-------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of ?-part.
*/
for (int k = less; k <= great; ++k) {
if (a[k] == pivot) {
continue;
}
int ak = a[k];
if (ak < pivot) { // Move a[k] to left part
a[k] = a[less];
a[less] = ak;
++less;
} else { // a[k] > pivot - Move a[k] to right part
while (a[great] > pivot) {
--great;
}
if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
++less;
} else { // a[great] == pivot
/*
* Even though a[great] equals to pivot, the
* assignment a[k] = pivot may be incorrect,
* if a[great] and pivot are floating-point
* zeros of different signs. Therefore in float
* and double sorting methods we have to use
* more accurate assignment a[k] = a[great].
*/
a[k] = pivot;
}
a[great] = ak;
--great;
}
}
/*
* Sort left and right parts recursively.
* All elements from center part are equal
* and, therefore, already sorted.
*/
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
}
}
該算法的實現(xiàn)了一種稱為“DualPivotQuicksort”的排序算法，中文可以翻譯為“雙樞軸快速排序”猾漫，可以看作是經(jīng)典快速排序算法的變體。算法的基本思路是：如果數(shù)組的數(shù)據(jù)量較少禽翼，則執(zhí)行插入排序就可以達到很好的效果礁哄，如果數(shù)據(jù)量較大夺脾，那么確定數(shù)組的5個分位點，選擇一個或兩個分位點作為“樞軸”，然后根據(jù)快速排序的思想進行排序婉弹。
根據(jù)算法的思路汉买，以上代碼也可以劃分為三個部分：
第一部分：
12-72行為第一部分威彰，該部分對數(shù)組進行插入排序舔痕。對于何時執(zhí)行插入排序，程序定義了常量INSERTION _SORT_THRESHOLD，如果數(shù)組長度小于這個常量叮雳，程序認為這是一個小規(guī)模的數(shù)組杨箭，采用插入排序算法進行處理捣郊，后面的代碼不再執(zhí)行稻艰；否則僧凤，程序執(zhí)行快速排序算法處理旋膳。這里的常量INSERTION _SORT_THRESHOLD程序定義其值為47。
這一部分對于插入排序也給出了一種改進的方案，基本思路是每次迭代過程中同時完成兩個元素的插入排序碱工，代碼的注釋給出了該算法的名稱—— pair insertion sort，中文可以譯為“雙插入排序”。代碼中第15-29行為經(jīng)典插入排序算法的實現(xiàn)，32-70行為雙插入排序算法的實現(xiàn)。下面簡要說明雙插入排序算法的思路蝙叛。
48-63行的循環(huán)代碼中用a1和a2兩個變量存儲每次迭代時要完成排序的兩個相鄰的元素淌铐。首先確保a1和a2的大小關(guān)系是a1≥a2拾碌。然后利用變量k遍歷a1和a2之前的元素，找到第一個小于a1的元素的位置防症，確定a1的位置炭玫，54-57行的while循環(huán)完成了這一步驟指么；由于a2≤a1，所以a2的位置一定在a1之前，因此，確定了a1的位置后接癌，k繼續(xù)遍歷椭符，此時的步驟和普通的插入排序是完全相同的有咨，59-62行的代碼完成了這一步驟婉商。
對于雙插入排序诗箍，有一種特殊情況，如果原數(shù)組的元素格式是奇數(shù)的話，那么最后一個元素就沒有元素與其配對完成插入排序汤求，因此裤唠，還需要額外進行一次插入排序來完成排序墓赴，這里的處理步驟和經(jīng)典插入排序也和經(jīng)典插入排序是完全相同的刊侯，65-79行的代碼完成了這個處理過程纲菌。
另外冬骚，為了提高算法效率庇麦，在算法開始前，我們可以跳過數(shù)組前面已經(jīng)有序的部分睡雇，從第一個無序的元素開始遍歷朴艰、插入蜘腌，31-38行的代碼完成了這個初始化過程金矛。
需要注意的是娶耍，48-63行的代碼中岳悟，對于變量k的值沒有進行數(shù)組邊界檢查爷肝，根據(jù)給出的代碼注釋何缓，現(xiàn)有的程序設(shè)計思路下，即使不對k變量進行數(shù)組越界的檢查，也一定不會發(fā)生異常身隐。這里的具體原因會在下文中說明，這里先略過。
第二部分：
74-108行為代碼的第二部分。如果數(shù)組比較大蚀瘸，那么就要采用快速排序的算法來處理苏章。本部分程序?qū)τ诳焖倥判蛩惴ǖ倪M行確定了分位點。分為點的確定思路是將數(shù)組長度劃分為7等份，然后確定5個分割點為3/14分位點曼尊、5/14分位點父叙、中點、9/14分位點以及11/14分位點，程序中分別記為：e1、e2析既、e3躬贡、e4、e5眼坏。分為點的確定方式如下圖：
確定分位點后， 90-107行代碼宰译，對于5個分位點的元素進行了排序檐蚜。
以上為第二部分的代碼，邏輯比較簡單囤屹。
第三部分：
109-336行為第三部分熬甚，本部分是這個方法的主體，也是快速排序算法的實現(xiàn)肋坚，以下為具體的實現(xiàn)思路乡括。
第三部分的算法實現(xiàn)又可以分為兩種情況：
情況一：
如果前面得到的5個分位點的值各不相同，那么就選擇e2和e4分為點作為快速排序的“樞軸”智厌，采用雙樞軸快速排序算法進行排序诲泌；否則，選擇e3铣鹏，作為樞軸敷扫，進行快速排序，這里雖然僅有一個樞軸點，但也和經(jīng)典的快速排序算法有一定的區(qū)別葵第。下文中首先介紹雙樞軸快速排序的實現(xiàn)绘迁。
113-267行為雙樞軸快速排序的實現(xiàn)，類似于經(jīng)典的快速排序算法卒密，每一輪遞歸的目的就是找到樞軸點pivot1 = e2 和 pivot2 = e4的正確位置缀台，當本輪遞歸結(jié)束時，連個樞軸點將整個數(shù)組劃分為3個部分哮奇，元素大小小于pivot1的部分膛腐、元素大小介于pivot1和pivot2之間(包含邊界)的部分以及元素大小大于pivot2的部分。如下圖：
137-188行的while循環(huán)實現(xiàn)了這一過程鼎俘，程序中用less變量記錄第一部分的邊界哲身，great變量記錄第3部分的邊界，循環(huán)變量k可指示了本輪迭代中待檢查的元素贸伐，此時勘天，基于less和k之間的元素就是第二部分的元素，基于k和great之間的元素則尚未檢查棍丐，如下圖：
根據(jù)當前檢查元素a[k]的結(jié)果误辑，又可以分為三種情況：
① 如果a[k]屬于第二部分沧踏，此時歌逢，不需要做任何操作，直接進行下一輪循環(huán)即可翘狱。
② 如果a[k]屬于第一部分秘案，此時，第一部分需要擴張潦匈，由于和第一部分相鄰的是第二部分阱高，此時第二部分需要向右“平移”以擴大第一部分，平移的方法是將第二部分最左邊的元素放置到最右邊茬缩，然后將左邊的空余位置中填入a[k]即可赤惊，如下圖：
159-166行代碼處理了以上過程。
③ 如果a[k]屬于第三部分凰锡，則第三部分需要擴張未舟，由于和第三部分相鄰的是未知的部分，因此a[great]可能屬于第二部分掂为，也可能屬于第一部分裕膀。這里程序首先取出a[great]元素，然后再確定a[great]的位置勇哗。
如果a[great]輸入第二部分昼扛，那么直接將其放在a[k]的位置即可：
如果a[great]屬于第一部分，此時需要擴張第一部分欲诺，同時將第二部分向右平移抄谐，處理方式和情況①類似渺鹦，如下：
168-185行代碼處理了以上過程。
為了提高算法效率蛹含，131-135行程序在迭代開始前對于數(shù)組進行了預(yù)處理海铆，找出已經(jīng)有序的第一部分和第三部分，迭代從第一個失序的元素開始挣惰。
程序在算法迭代開始前卧斟，先將兩個樞軸值從數(shù)組中抽出，并將數(shù)組的首末元素插入到兩個樞軸點的空余位置憎茂，然后開始迭代珍语，迭代完成后，在將兩個樞軸值插入到第一部分的末尾和第三部分的首部竖幔，就找到了兩個樞軸值的正確位置板乙。128行、129行代碼將樞軸值從數(shù)組中取出拳氢，并將首末元素填入募逞；190、191行代碼將樞軸值重新插入到數(shù)組中馋评。
找到樞軸值的正確位置后放接，接下來類似于經(jīng)典快速排序，遞歸地調(diào)用本方法對樞軸值劃分的3個部分進行排序留特。194纠脾、195行代碼對于第一、第三部分進行了排序蜕青。而對于第二部分苟蹈，程序做了一些優(yōu)化，如下：
在某些情況下右核，樞軸值的取值可能距離數(shù)據(jù)的中心點較遠慧脱，即，通過156-187行的迭代后贺喝，只有少部分數(shù)據(jù)落在了第一菱鸥、第三部分，大部分數(shù)據(jù)依然留在第二部分搜变，此時直接對第二部分排序效率可能較低采缚，因此程序再次對于部分進行篩選，將第二部分又劃分為3個子區(qū)間：等于pivot1的區(qū)間挠他、介于pivot1和pivot2(不包含邊界)的部分扳抽、等于pivot2的區(qū)間，劃分完成后，只需要對第二子區(qū)間的數(shù)據(jù)進行遞歸調(diào)用方法排序即可贸呢。從某種程度上镰烧，這樣的優(yōu)化減少了第二部分參加遞歸調(diào)用的數(shù)據(jù)量。
197-264行代碼實現(xiàn)了這一優(yōu)化楞陷，代碼的邏輯基本和前面137-187行的循環(huán)相同怔鳖，這里不再贅述：
完成優(yōu)化后，267行代碼完成了對于中部區(qū)間序列的排序固蛾。
情況二：
上文中情況一為5個分位點個各不相同的處理情況结执，而對于5個分位點如果存在兩個分位點的值相同，程序給出了另一種策略艾凯，此時不再使用雙樞軸献幔，而是僅選擇 pivot = e3 分位點作為唯一的樞軸點，不同于經(jīng)典快速排序算法的是趾诗，這種情況下蜡感，算法依舊將數(shù)組劃分為三個部分：小于pivot的部分、等于pivot的部分以及大于pivot的部分恃泪。
276-327行代碼給出了情況二的實現(xiàn)郑兴，代碼邏輯基本和前面的137-187行的迭代代碼相同，這里也不再贅述：
334贝乎、335行代碼對于第一部分和第二部分通過遞歸調(diào)用方法進行排序情连，此時，不同于情況一糕非，第二部分已經(jīng)是有序的蒙具，因此不需要對第二部分優(yōu)化球榆，也不需要對第二部分再次遞歸調(diào)用方法朽肥。
最后還有一個小問題需要說明，那就是前面提到的40-70行代碼雙插入排序不需要檢查k值數(shù)組越界的原因持钉。通過觀察可以發(fā)現(xiàn)衡招，這部分代碼只有在leftmost值為false的情況下，即待排序數(shù)據(jù)的范圍的不是整個數(shù)組的最左邊時每强，才會執(zhí)行始腾。觀察代碼2，可以發(fā)現(xiàn)調(diào)用到代碼3方法的地方(代碼2:13空执、39浪箭、50行),傳入的foremost的值都是true，因此辨绊，如果程序執(zhí)行到了40-70行的代碼奶栖，此時該方法的調(diào)用者一定還是該方法本身(代碼3：194、195、267宣鄙、334袍镀、335行),而此時，如果傳入的leftmost為false冻晤，那么可以保證整個數(shù)組的最小值一定不再這個區(qū)間內(nèi)苇羡，因此插入排序過程中一定會在遍歷到數(shù)組首部之前找到待插入元素的位置，也就一定不會出現(xiàn)數(shù)組越界的異常情況鼻弧。
以上就是JDK中對于數(shù)據(jù)數(shù)組排序方法：Arrays.sort()的實現(xiàn)方式设江。
下面簡單說一說筆者第一次閱讀JDK源碼遇到的問題和一些心得體會：
(1) 編代碼加注釋的重要性：JDK的源代碼給出了很詳盡的注釋，這些注釋對于筆者閱讀代碼過程中提供了很大的幫助攘轩。程序代碼是給開發(fā)者閱讀的绣硝，并不是給計算機，編碼過程中添加一些注釋有助于其他開發(fā)人員閱讀和理解撑刺。
(2)JDK的編碼風格：筆者認為鹉胖，JDK源碼的編碼風格比較奇怪，例如：原本對于for循環(huán)够傍，有一個不成文的規(guī)定是：循環(huán)頭的三個部分最好是對一個變量進行操作甫菠，而通過閱讀發(fā)現(xiàn)，JDK的源碼中對于for循環(huán)有各種各樣的風格冕屯，導致筆者感覺代碼非臣庞眨晦澀難懂。這種編碼風格筆者個人不提倡安聘。但是痰洒，這也充分表明代碼的作者編程功力非常深厚，對于Java語法的應(yīng)用可以說是如魚得水浴韭、融會貫通丘喻。所以，相比這些大牛念颈，我們需要學習的東西還有很多泉粉。
(3)代碼2中37-42行代碼：當數(shù)組中出現(xiàn)長度超過MAX_RUN_LENGTH == 33的等值序列時，就直接調(diào)用快速排序榴芳，這樣設(shè)計的用意筆者依舊不明白嗡靡。
(4)對于代碼3中的第二部分劃分分為點的代碼，分為點選取的依據(jù)是什么窟感？如果僅僅是為了雙樞軸快速排序算法尋找樞軸點的話讨彼，直接選擇兩個三等分點作為樞軸點也是可以達到相同的效果的。分位點的選取依據(jù)筆者尚不明白柿祈。
(5)筆者認為代碼3中的第三部分有些冗余哈误，如果將159和167行代碼中的判定條件中包含等于酣难，那么當循環(huán)結(jié)束時，第二部分就已經(jīng)優(yōu)化完成黑滴，就不再需要213-265行的中部優(yōu)化代碼憨募；如果將309行的判定條件也包含了等于，那么情況二的排序算法和經(jīng)典的快速排序算法就完全相同了袁辈。之所以是現(xiàn)在的設(shè)計方式菜谣，筆者認為可能是為了盡可能減少參與遞歸調(diào)用處理的數(shù)據(jù)量，由于等值序列已經(jīng)是有序序列晚缩，因此尾膊，將其從程序處理的數(shù)據(jù)中抽出不會改變程序的結(jié)果，但是程序處理的數(shù)據(jù)量會有減少荞彼，效率就會提高冈敛。但是筆者目前無法用更嚴密的方式證明這樣的策略可以提高算法效率。
(6)代碼3的策略選擇問題鸣皂，為何只有五個分位點各不相同時才能使用雙樞軸快速排序算法抓谴，這樣設(shè)計的用意是什么？筆者尚不明白寞缝。
(7)雙樞軸快速排序算法相對于經(jīng)典快排的優(yōu)越性：根據(jù)代碼中的注釋癌压，雙樞軸快速排序算法由于經(jīng)典快排，但是筆者目前無法給出準確的證明荆陆，關(guān)于這一點滩届，還需要參考更多的資料。
