印排序后的数组元素
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 (high - low < DIVISION) {//当长度小于分界点时调用快速排序
while (low < high) {
int pivot = partition(low, high, array); // 找到枢轴记录的下标
quickSort(low, pivot - 1, array); // 对低子表进行递归排序
low = pivot + 1; // 尾递归
}
}
}
/**
* 优化后快速排序的核心程序,枢轴记录用了三取一，去前中后三个数中间那个
*
* @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--;
}
array[low] = array[high]; // 把比枢轴记录小的值赋给low下标的记录
while (low < high && array[low] <= pivotKey) {
low++;
}
array[high] = array[low]; // 把比枢轴记录大的值赋给high下标的记录
array[low] = pivotKey; // 然后将枢轴记录赋给low
}
return low; // 返回枢轴记录的下标
}
/**
* 内部实现，用于交换数组的两个引用值
*
* @param beforeIndex
* @param afterIndex
* @param arr
*/
private void swap(int oneIndex, int anotherIndex, int[] array) {
int temp = array[oneIndex];
array[oneIndex] = array[anotherIndex];
array[anotherIndex] = temp;
}
4.最终优化：
[java]
/**
* 最终优化的快速排序法
*
* @author PingCX
*
*/
public class QuickSortOptAll {
/**
* 定义一个分界点常量
*/
private final int DIVISION = 50;
public static void main(String[] args) {
QuickSortOptAll qComplete = new QuickSortOptAll();
int[] array = { 25, 36, 21, 45, 13 };
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 (high - low > DIVISION) {//当长度小于分界点时调用快速排序
while (low < high) {
int pivot = partition(low, high, array); // 找到枢轴记录的下标
quickSort(low, pivot - 1, array); // 对低子表进行递归排序
low = pivot + 1; // 尾递归
}
}else {
insertSort(array);
}
}
/**
* 优化后快速排序的核心程序,枢轴记录用了三取一，去前中后三个数中间那个
*
* @param low