public class QuickSort {
//基本框架，dp为一次快排，中轴点pivot在数组中的位置
public void quickSort(int[] a,int left,int right){
int dp;
if (left < right) {
dp = partition(a, left, right);
quickSort(a, left, dp - 1);
quickSort(a, dp + 1, right);
}
}
//关键的一次快排函数，取第一个点为比较值点，前后两个指针移动比较，直到指针相遇为止，返回中轴点位置
public int partition(int n[], int left, int right) {
int pivot = n[left];
while (left < right) {
while (left < right && n[right] >= pivot)
right--;
if (left < right){
n[left] = n[right];
left++;
}
while (left < right && n[left] <= pivot)
left++;
if (left < right){
n[right] = n[left];
right--;
}
}
n[left] = pivot;
return left;
}
public static void main(String[] args){
QuickSort q = new QuickSort();
int[] array = { 57, 68, 52,72,28,96,33,24,19 };
q.quickSort(array, 0, array.length-1);
for(int element :array){
System.out.print(element+" ");
}
}
快排的思想是递归，一次快排函数是使用的双指针。一次快排中，任选一个轴点，一次快排后，左边的元素比它小，右边的元素比它大。
快排比较容易晕，举例子过程会比较容易理解
- 原始测试用例57, 68, 52,72,28,96,33,24,19
选第一个元素为轴点，代码中的例子第一次快排的结果为：
19 24 33 52 28 57 96 72 59 68
-
具体这次快排结果的过程为：
一次快排函数过程
JDK里提供排序实现Arrays.sort()
jdk1.6 是默认的快速排序
jdk1.7 是双轴快速排序DualPivotQuicksort
jdk1.8 是改进的双轴快排，还提供的parallelSort（并行归并排序），在部分元素已经有序的情况下效率高
