看源碼時(shí)專門瞄了下排序算法旨枯，跟著學(xué)一下。JDK的排序是 插入排序扇谣、快排揉一起的昧捷，下面學(xué)下快速排序。在JDK中當(dāng)待排序的元素個(gè)數(shù)小于 ** 286 ** 時(shí)使用快速排序罐寨，當(dāng)待排序的元素個(gè)數(shù)小于 ** 47 ** 時(shí)使用插入排序靡挥。JDK源碼類：DualPivotQuicksort.java
本文地址：http://www.reibang.com/p/a7ceb2dc62ca
由于JDK的算法寫的怪怪的（個(gè)人感覺(jué)），所以不參照它的代碼鸯绿，只參照它的思想跋破。
對(duì)于快速排序，JDK先采用雙軸快排瓶蝴，即：取5個(gè)元素毒返，按順序排好，然后取第二個(gè)和第四個(gè)元素作為軸開(kāi)始排序舷手。如果這五個(gè)元素恰好相等拧簸，則使用中間的元素作為軸開(kāi)始快排（傳統(tǒng)的快排）
- 先來(lái)看下傳統(tǒng)的快排：?jiǎn)屋S快排，軸的選擇有很多種男窟，第一個(gè)元素狡恬，最后一個(gè)元素，中心位置元素蝎宇，隨機(jī)位置元素弟劲，取首尾中3個(gè)元素中的中間值等，也可以參照J(rèn)DK取5個(gè)元素的中值作為軸姥芥。此處以取首尾中3個(gè)元素中的中間值為例
public static void basicSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
basicSort(array, 0, array.length - 1);
}
private static void basicSort(int[] array, int low, int high) {
if (low >= high) {
return;
}
// 這里通常判斷下待排序元素的個(gè)數(shù)兔乞，比如小于47個(gè)使用插入排序，以提高性能
// .....
// 單軸快排凉唐，核心在取軸這
int position = basicPosition(array, low, high);
basicSort(array, low, position - 1);
basicSort(array, position + 1, high);
}
private static int basicPosition(int[] array, int low, int high) {
// 初始化軸數(shù)據(jù)庸追，獲取軸數(shù)據(jù)并放到數(shù)組第一個(gè)位置
initPivotData(array, low, high);
int pivotData = array[low]; // 軸數(shù)據(jù)
int begin = low, end = high;
while (begin < end) {
while (array[begin] <= pivotData && begin < high) {
begin++;
}
while (array[end] > pivotData && end >= low) {
end--;
}
if (begin < end) {
swap(array, begin, end);
}
printArray(array);
}
if (end != low) {
swap(array, low, end);
printArray(array);
}
return end;
}
// 這里將3各元素做升序排序，并將中值交換到數(shù)組第一個(gè)元素處
private static void initPivotData(int[] array, int low, int high) {
int mid = low + (high - low) / 2;
if (array[mid] > array[high]) {
swap(array, mid, high);
}
if (array[low] > array[high]) {
swap(array, low, high);
}
if (array[mid] > array[low]) {
swap(array, mid, low);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
- 下面看下JDK的雙軸快排台囱，選兩個(gè)軸淡溯，排序方式，比軸1小的數(shù)據(jù)放到軸1左側(cè)簿训，比軸2大的數(shù)據(jù)放到軸2右側(cè)咱娶，其余的數(shù)據(jù)在軸1和軸2之間
public static void dualPivotSort(int[] array) {
dualPivotSort(array, 0, array.length-1);
}
// 參照J(rèn)DK取軸的方法，該方法未使用
private static void initdualPivotData(int[] array, int low, int high) {
int length = high - low + 1; // 待排序元素的個(gè)數(shù)
int seventh = (length >> 3) + (length >> 6) + 1; // 7 等份
// 取5個(gè)節(jié)點(diǎn)
int e3 = (low + high) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
// 對(duì)這5各元素做插入排序强品，然后去e2和e4作為軸
}
private static void dualPivotSort(int[] array, int lowIndex, int highIndex) {
if (highIndex <= lowIndex) return;
// initdualPivotData(array, lowIndex, highIndex);
int pivot1 = array[lowIndex];
int pivot2 = array[highIndex];
// 確保 pivot1 < pivot2
if (pivot1 > pivot2) {
swap(array, lowIndex, highIndex);
pivot1 = array[lowIndex];
pivot2 = array[highIndex];
}
else if (pivot1 == pivot2) {
while (pivot1 == pivot2 && lowIndex < highIndex){
lowIndex++;
pivot1 = array[lowIndex];
}
}
int i = lowIndex + 1;
int lt = lowIndex + 1;
int gt = highIndex - 1;
while (i <= gt) {
if (array[i] < pivot1) {
// 小于軸1膘侮，則將數(shù)據(jù)交換到軸的左側(cè)
swap(array, i++, lt++);
}
else if (pivot2 < array[i]) {
// 大于軸2，則將數(shù)據(jù)交換到軸的右側(cè)
swap(array, i, gt--);
}
else {
i++; // 其他不處理的榛，索引向后移動(dòng)1
}
}
/* 都交換之后
* 將軸1交換到中間部分的左側(cè)琼了；軸2交換到中間部分的右側(cè)
* 這樣確保左側(cè)都小于軸1，右側(cè)都大于軸2
*/
swap(array, lowIndex, --lt);
swap(array, highIndex, ++gt);
// 普通的快排夫晌，只需對(duì)軸兩側(cè)遞歸處理
// 這里是雙軸快排雕薪，所以要對(duì)左側(cè)昧诱、中間、右側(cè)分別遞歸處理
dualPivotSort(array, lowIndex, lt - 1);
dualPivotSort (array, lt + 1, gt - 1);
dualPivotSort(array, gt + 1, highIndex);
}
- 快速排序還有一種方式用的比較多所袁，3路排序盏档。該方案也是選一個(gè)軸，比軸小的數(shù)據(jù)在軸的左側(cè)纲熏，比軸大的數(shù)據(jù)在軸的右側(cè)妆丘，中間是與軸相等的數(shù)據(jù)。
public static void threeWaySort(int[] array) {
threeWaySort(array, 0, array.length-1);
}
private static void threeWaySort(int[] array, int low, int high) {
if (high <= low)
return;
// 初始化軸數(shù)據(jù)局劲，獲取軸數(shù)據(jù)并放到數(shù)組第一個(gè)位置（使用第一種快排的方式獲壬准稹）
initPivotData(array, low, high);
int lt = low; // 記錄最后一次發(fā)現(xiàn)低值的位置
int gt = high; // 記錄最后一次發(fā)現(xiàn)高值的位置
int i = low + 1;// 用于從左側(cè)遍歷到右側(cè)
int pivotIndex = low;
int pivotValue = array[pivotIndex];
while (i <= gt) {
// 小于軸，交換到左側(cè)
if (array[i] < pivotValue) {
swap(array, i++, lt++);
}
// 大于軸鱼填，交換到右側(cè)
else if (pivotValue < array[i]) {
swap(array, i, gt--);
}
else {
i++; // 相等不做處理
}
}
// 這里與單軸快排一樣
threeWaySort(array, low, lt - 1);
threeWaySort(array, gt + 1, high);
}
