看源码时专门瞄了下排序算法，跟着学一下。JDK的排序是 插入排序、快排揉一起的，下面学下快速排序。在JDK中当待排序的元素个数小于 ** 286 ** 时使用快速排序，当待排序的元素个数小于 ** 47 ** 时使用插入排序。JDK源码类：DualPivotQuicksort.java
本文地址：http://www.jianshu.com/p/a7ceb2dc62ca
由于JDK的算法写的怪怪的（个人感觉），所以不参照它的代码，只参照它的思想。
对于快速排序，JDK先采用双轴快排，即：取5个元素，按顺序排好，然后取第二个和第四个元素作为轴开始排序。如果这五个元素恰好相等，则使用中间的元素作为轴开始快排（传统的快排）
- 先来看下传统的快排：单轴快排，轴的选择有很多种，第一个元素，最后一个元素，中心位置元素，随机位置元素，取首尾中3个元素中的中间值等，也可以参照JDK取5个元素的中值作为轴。此处以取首尾中3个元素中的中间值为例
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;
}
// 这里通常判断下待排序元素的个数，比如小于47个使用插入排序，以提高性能
// .....
// 单轴快排，核心在取轴这
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) {
// 初始化轴数据，获取轴数据并放到数组第一个位置
initPivotData(array, low, high);
int pivotData = array[low]; // 轴数据
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各元素做升序排序，并将中值交换到数组第一个元素处
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的双轴快排，选两个轴，排序方式，比轴1小的数据放到轴1左侧，比轴2大的数据放到轴2右侧，其余的数据在轴1和轴2之间
public static void dualPivotSort(int[] array) {
dualPivotSort(array, 0, array.length-1);
}
// 参照JDK取轴的方法，该方法未使用
private static void initdualPivotData(int[] array, int low, int high) {
int length = high - low + 1; // 待排序元素的个数
int seventh = (length >> 3) + (length >> 6) + 1; // 7 等份
// 取5个节点
int e3 = (low + high) >>> 1; // The midpoint
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
// 对这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，则将数据交换到轴的左侧
swap(array, i++, lt++);
}
else if (pivot2 < array[i]) {
// 大于轴2，则将数据交换到轴的右侧
swap(array, i, gt--);
}
else {
i++; // 其他不处理，索引向后移动1
}
}
/* 都交换之后
* 将轴1交换到中间部分的左侧；轴2交换到中间部分的右侧
* 这样确保左侧都小于轴1，右侧都大于轴2
*/
swap(array, lowIndex, --lt);
swap(array, highIndex, ++gt);
// 普通的快排，只需对轴两侧递归处理
// 这里是双轴快排，所以要对左侧、中间、右侧分别递归处理
dualPivotSort(array, lowIndex, lt - 1);
dualPivotSort (array, lt + 1, gt - 1);
dualPivotSort(array, gt + 1, highIndex);
}
- 快速排序还有一种方式用的比较多，3路排序。该方案也是选一个轴，比轴小的数据在轴的左侧，比轴大的数据在轴的右侧，中间是与轴相等的数据。
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;
// 初始化轴数据，获取轴数据并放到数组第一个位置（使用第一种快排的方式获取）
initPivotData(array, low, high);
int lt = low; // 记录最后一次发现低值的位置
int gt = high; // 记录最后一次发现高值的位置
int i = low + 1;// 用于从左侧遍历到右侧
int pivotIndex = low;
int pivotValue = array[pivotIndex];
while (i <= gt) {
// 小于轴，交换到左侧
if (array[i] < pivotValue) {
swap(array, i++, lt++);
}
// 大于轴，交换到右侧
else if (pivotValue < array[i]) {
swap(array, i, gt--);
}
else {
i++; // 相等不做处理
}
}
// 这里与单轴快排一样
threeWaySort(array, low, lt - 1);
threeWaySort(array, gt + 1, high);
}
网友评论