看源码时专门瞄了下排序算法，跟着学一下。JDK的排序是 插入排序、快排揉一起的，先来学下插入排序。在JDK中当待排序的元素个数小于 ** 47 ** 时使用插入排序。JDK源码类：DualPivotQuicksort.java
本文地址：http://www.jianshu.com/p/98539ba3fd86
- JDK中，leftmost为true时使用的是传统的插入排序（跟下面代码大同小异）
主要思想是：从i=2起直至i=n为止，依次将data[i]插入当前的有序区data[1..i-1]中。最快O(n)，最坏O(n*n)
public static void sort(int[] array) {
int j, target;
for (int i = 1; i < array.length; i++) {
j = i;
target = array[i];
while (j > 0 && target < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
}
- JDK中，leftmost为false时使用的是成对插入排序。
主要思想跟上面差不多，只不过一次拿两个元素，先用其中一个较大的元素向前遍历插入，然后再用较小的元素继续向前遍历插入，这样较小的元素不必再次走一遍较大元素走过的路。对于元素个数为奇数的情况，最后一个元素单独走一次插入排序即可。（JDK的跟这个有点区别）
JDK中的写法不能直接拿来使用，改写了一下。
public static void pairSort(int[] array) {
// 参数检测
if (array == null || array.length < 2) {
return;
}
int right = array.length;
// 如果元素个数为奇数，则数组长度 - 1
boolean adjust = false;
if (right % 2 == 1) {
adjust = true;
--right;
}
// 处理前两个元素
if (array[0] > array[1]) {
int temp = array[0];
array[0] = array[1];
array[1] = temp;
}
// 排序，k = i - 1
for (int i = 2, k = 1; i < right; i += 2, k = i - 1) {
// 取值并保证 low < high
int low = array[i], high = array[i + 1];
if (low > high) {
low = high;
high = array[i];
}
// 插入较大的值
while (k >= 0 && high < array[k]) {
array[k + 2] = array[k];
k--;
}
array[k + 2] = high;
// 插入较小的值
while (k >= 0 && low < array[k]) {
array[k + 1] = array[k];
k--;
}
array[k + 1] = low;
}
// 处理最后一个元素
if (adjust) {
int begin = array.length - 1;
int value = array[begin];
while (--begin >= 0 && array[begin] > value) {
array[begin + 1] = array[begin];
}
array[begin + 1] = value;
}
}
经测试，确实比传统的插入排序要快，快多少跟数组元素中的数据有关。
