排序的尾递归调用
*
* @param low
* @param high
* @param array
*/
private void quickSort(int low, int high, int... array) {
if (high - low > DIVISION) {//当长度小于分界点时调用快速排序
while (low < high) {
int pivot = partition(low, high, array); // 找到枢轴记录的下标
quickSort(low, pivot - 1, array); // 对低子表进行递归排序
low = pivot + 1; // 尾递归
}
}else {
insertSort(array);
}
}
@DIVISION是一个分界点常量：
[java]
/**
* 定义一个分界点常量
*/
private final int DIVISION = 50;
@insertSort(array)：
[java]
/**
* 直接插入排序的核心程序
* @param array
*/
public void insertSort(int... array) {
int length = array.length;
// 此循环从1开始，就是将0下标的元素当做一个参照
for (int i = 1; i < length; i++) {
if (array[i] < array[i - 1]) { // 将当前下标的值与参照元素比较，如果小于就进入里面
int vacancy = i; // 用于记录比较过程中那个空缺出来的位置
int sentry = array[i]; // 设置哨兵，将当前下标对应的值赋给哨兵
// 这个循环很关键，从当前下标之前一个元素开始倒序遍历，比较结果如果比当前大的，就后移
for (int j = i - 1; j >= 0 && array[j] > sentry; j--) {
vacancy = j;
array[j + 1] = array[j]; // 后移比当前元素大的元素
}
array[vacancy] = sentry; // 将哨兵，也就是当前下标对应的值置入空缺出来的位置
}
}
}
下面是四种优化版本的完整代码实现：
1.枢轴选取优化：
[java]
/**
* 优化枢轴值的快速排序法
*
* @author PingCX
*
*/
public class QuickSortOptPivot {
public static void main(String[] args) {
QuickSortOptPivot qComplete = new QuickSortOptPivot();
int[] array = { 9, 5, 6, 8, 4, 3, 2, 7, 1 };
System.out.println(Arrays.toString(array));
qComplete.quickSort(array);// 调用快速排序的方法
System.out.println(Arrays.toString(array));// 打印排序后的数组元素
System.out.println(qComplete.getMid(25, 90, 13));
}
/**
* 快速排序的入口
*
* @param array
*/
public void quickSort(int... array) {
quickSort(0, array.length - 1, array);
}
/**
* 快速排序的递归调用
*
* @param low
* @param high
* @param array
*/
private void quickSort(int low, int high, int... array) {
if (low < high) {
int pivot = partition(low, high, array); // 找到枢轴记录的下标
quickSort(low, pivot - 1, array); // 对低子表进行递归排序
quickSort(pivot + 1, high, array); // 对高子表进行递归排序
}
}
/**
* 优化后快速排序的核心程序,枢轴记录用了三取一，去前中后三个数中间那个
*
* @param low
* @param high
* @param array
* @return 返回枢轴记录
*/
private int partition(int low, int high, int... array) {
int mid = (low + high) / 2;
//枢轴记录三取一，优化的代码，用于待排序数组元素不是很大的时候
{
if (array[low] > array[high]) {
//交换左端与右端的记录，保证左端较小
swap(low, high, array);
}
if (array[mid] > array[high]) {
//交换中间与右端的记录，保证中间较小
swap(mid, high, array);
}
if (array[mid] > array[low]) {
//交换左端与中间的记录，保证左端较小
swap(mid, low, array);
}
}
int pivotKey = array[low]; // 将三取一后的中间值作为枢轴记录
while (low < high) {
while (low < high && array[high] >= pivotKey) {
high--;
}
swap(low, high, array); // 把比枢轴记录小的值交换到低端
while (low < high && array[low] <= pivotKey) {
low++;
}
swap(low, high, arr