一、快排原理二、实例操作三、实战代码四、总结
一、快排原理
- 从待排序区间选择一个数，作为基准值（pivot）；遍历整个待排序区间，将比基准值小的（可等于）放到基准值左边，将比基准值大的（可等于）放到基准值右边；采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间长度=1（说明已有序）或者小区间长度=0(说明没有数据可排了).
我们现在有如下数据（红字代表数组下标），要求从小到大排序。
我们定义3个变量start、end、tmp，这里默认start在下标0的位置，end在下标9的位置。
将start位置的数据（这里是6）拿出来，放到tmp里，从end位置开始向前找，如果end位置的数据比tmp里的数据大，end–，反之，end位置的数据给到start位置
示例如下：
1.start位置数据给到tmp
2.判断：end位置上是8,tmp位置上是6，8比6大，end–
3.判断：end位置上是10,tmp位置上是6，10比6大，end–
4.判断：end位置上是5,tmp位置上是6，5比6小，end数据给到start位置
到这里，start位置的空补上了，end又空出来了，怎么办？举一反三——前面end是往前找比tmp小的数据，那我们start就是往后找比tmp大的数据
示例如下：
5.判断：start位置上是5,tmp位置上是6，5比6小，start++
6.判断：start位置上是1,tmp位置上是6，1比6小，start++
7.判断：start位置上是2,tmp位置上是6，2比6小，start++
8.判断：start位置上是7,tmp位置上是6，7比6大，start位置的值给end位置
到这里start又空出来位置了，end继续向前找比tmp小的数据
9.判断：end位置上是7,tmp位置上是6，7比6大，end–
10.判断：end位置上是4,tmp位置上是6，4比6小，end位置数据给start位置
到这里，end位置再次空缺，start开始向后走，找比tmp大的数据
11.判断：start位置上是4,tmp位置上是6，4比6小，start++
12.判断：start位置上是9,tmp位置上是6，9比6大，start位置数据给end位置
start再次空出，同样的，继续end往前找比tmp小的
11.判断：end位置上是9,tmp位置上是6，9比6大，end–
12.判断：end位置上是3,tmp位置上是6，3比6小，end位置数据给start位置
end位置再次空出，我们老样子，start向后找比tmp大的，我们start往后一走，发现与end相遇了，这个时候，把tmp里的值给start（end也一样，此时end位置就是start位置）
这个end与start相遇的位置，我们也叫基准位置，这里用变量pivot表示
走完上面的全部步骤，我们发现，基准左边的数<=基准<=基准右边的数
那会有同学说：“啊，你这走完一遍，也没有全部从小到大排序啊！”，请不要急，刚刚只是第一步。找到基准之后，分而治之，分别重复上面操作递归基准的左边和右边。
（这里仅以左边为例）
1.start的数据放到tmp里：
2.end向前找比tmp小的数据
判断：end位置上是3,tmp位置上是5，3比5小，end位置数据给start位置
3.start开始向后找比tmp大的数据
判断：start位置上是3,tmp位置上是5，3比5小，start++
判断：start位置上是1,tmp位置上是5，1比5小，start++
判断：start位置上是2,tmp位置上是5，2比5小，start++
判断：start位置上是4,tmp位置上是5，4比5小，start++
4.start与end相遇，tmp位置数据给到start（end也可以，两者都一样）
到这里新的基准产生。
再对新基准的左右进行同样的递归，
5的左边：（这里省略上述同样操作）
5的右边：没有数据，也就是小区间长度=0(说明没有数据可排了).
ps:上述方法也就是常说的挖坑法
三、实战代码代码如下（示例）：
public static void quickSort(int[]array){
//这里是为了接口统一，读者也可以直接用里面的quick
quick(array,0, array.length-1);
}
public static void quick(int[]arr,int left,int right){
if(left>=right){
return;
}
int pivot=partition(arr,left,right);//找基准
quick(arr,left,pivot-1);//递归基准坐边
quick(arr, pivot+1, right);//递归基准右边
//找基准类似一棵二叉树
}
private static int partition(int[]arr,int start,int end){
//找基准，挖坑法
int tmp=arr[start];
while(start=tmp){
//为什么多加一个start=tmp一直成立,end一直--，最后越界访问到arr[-1]
end--;
}
//end下标遇到了tmp的值
arr[end]=arr[start];
}
arr[start]=tmp;
//相遇位置就是基准位置
return start;//这里start和end一样，return end也可以
}
public static void main(String[] args) {
int[]arr={6,1,2,7,9,3,4,5,10,8};
quickSort(arr);
System.out.println(Arrays.toString(arr));
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}
运行结果如下：
四、总结
- 在待排序区间选择一个基准值（我这里是选择最左边的数据）做循环与递归，使得小的数在基准左，大的数在基准右继续分治处理基准左边和右边的区间
