一、快排原理

从待排序区间选择一个数，作为基准值（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){//这里是为了接口统一，读者也可以直接用里面的quickquick(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<end){while(start<end&&arr[end]>=tmp){//为什么多加一个start<end?//防止出现1234这种序列，tmp=1,arr[tmp]>=tmp一直成立,end一直--，最后越界访问到arr[-1]end--;}//end下标遇到了<tmp的值arr[start]=arr[end];while(start<end&&arr[start]<=tmp){//为什么多加一个start<end?//防止出现4321这种序列，tmp=4,arr[start]<=4一直成立，start一直++,最后越界访问到arr[arr.length]start++;}//start下标遇到了>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]}