原理
快速排序运用了递归的思想。 以升序为例，
- 在一趟排序过程中，取一个标准值，将小于标准值放到左边，不小于标准值的放到右边，最后返回标准值所在的位置middle
- 对左边(start ~ middle)部分进行单次排序（递归）
- 对右边(middle + 1 ~ end) 部分进行单次排序（递归）
- 对直到start >= end，排序结束。
复杂度分析
平均时间复杂度为O(n*㏒₂n)，每次将数据源对半分
时间复杂度最坏为O(n^2), 数据源一开始就是有序状态，在进行数据源分割的时候总是分为1 和n-1
空间复杂度为 O(㏒₂n)，递归所需栈空间
不稳定
代码实现
public void sort(int[] a){
qsort(a, 0, a.length - 1);
}
private void qsort(int[] a, int start, int end){
if (start >= end) {//递归出口
return ;
}
int middle = stepSort(a, start, end);//单次排序
qsort(a, start, middle);//左边递归
qsort(a, middle + 1, end);//右边递归
}
/**
* 单次排序
* 本次排序结束，左边的值<标准值<=右边的
* return 标准值所在位置
**/
private int stepSort(int[] a, int start, int end){
int std = a[start];
while (start < end){
while (start < end && a[end] >= std){//找到右边第一个比标准值小的位置
end--;
}
a[start] = a[end];//放到左侧
while (start < end && a[start] < std){//找到左边第一个不小于标准值的位置
start++;
}
a[end] = a[start];
}
a[start] = std;
return start;
}
