基本思想
1．先从数列中取出一个数作为基准数。
2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边（分区过程）。
3．再对左右区间重复第二步，直到各区间只有一个数。
算法实现
private static void quickSort(int a[], int left, int right) {
if (left > right) {
return;
}
int border = partition(a, left, right);
quickSort(a, left, border - 1);
quickSort(a, border + 1, right);
}
/**
* 循环分区过程:
* 1. 从左到右找到一个比基准数大的位置i
* 2. 从右到左找到一个比基准数小的位置j
* 3. 交互i,j的数值位置
* <p>
* 退出条件：
* i==right(到最右边都没找到比基准数大的位置)
* j==left（到最左边都没找到比基准数小的位置）
* i>j j之后的都比基准数大，不用再继续
* <p>
* 退出后的操作：
* 交换left（即基准数的位置）和j的位置，交换之后，j左边的都小于基准数，j右边的都大于基准数，j为下次分区的边界
* 返回j的位置
*/
private static int partition(int[] a, int left, int right) {
int i = left, j = right + 1;
int v = a[left];
while (true) {
while (a[++i] <= v) {
if (i == right) {
break;
}
}
while (a[--j] >= v) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
exchange(a, i, j);
}
exchange(a, left, j);
return j;
}
private static void exchange(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
测试
public static void main(String[] args) {
int a[] = {314, 1234, 34, 1, 234, 2341, 23, 434};
quickSort(a, 0, a.length - 1);
Arrays.stream(a).forEachOrdered(k -> {
System.out.print(k);
System.out.print(",");
});
}
//output:
1,23,34,234,314,434,1234,2341,
总结
快速排序在平均状况下，排序N个项目要Ο(N*logN)次比较。在最坏状况下则需要Ο(N2)次比较，但这种况并不常见。快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率比较高，因此经常被采用，快速排序的分治法思想也很常用。
优化
1.基准数的选择（随机选择或取数列中间数）
2.区间内数据较少时直接用另的方法排序以减小递归深度
这里有很详细的动画，可以查看快排详细过程：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html