以一个数组作为示例，取区间第一个数为基准数。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
初始时，i = 0; j = 9; temp = a[i] = 72
由于已经将 a[0] 中的数保存到 temp 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。
从 j 开始向前找一个比 temp 小或等于 temp 的数。当 j = 8，符合条件，将 a[8] 挖出再填到上一个坑 a[0] 中。
a[0] = a[8]; i++; 这样一个坑 a[0] 就被搞定了，但又形成了一个新坑 a[8]，这怎么办了？简单，再找数字来填 a[8] 这个坑。这次从i开始向后找一个大于 temp 的数，当 i = 3，符合条件，将 a[3] 挖出再填到上一个坑中 a[8] = a[3]; j--;
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
i = 3; j = 7; temp = 72
再重复上面的步骤，先从后向前找，再从前向后找。
从 j 开始向前找，当 j = 5，符合条件，将 a[5] 挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当 i = 5 时，由于 i==j 退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将 temp 填入 a[5]。
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
可以看出 a[5] 前面的数字都小于它，a[5] 后面的数字都大于它。因此再对 a[0…4] 和 a[6…9] 这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1．i = L; j = R; 将基准数挖出形成第一个坑 a[i]。
2．j-- 由后向前找比它小的数，找到后挖出此数填前一个坑 a[i] 中。
3．i++ 由前向后找比它大的数，找到后也挖出此数填到前一个坑 a[j] 中。
4．再重复执行 2，3 二步，直到 i==j，将基准数填入 a[i] 中。
作者：nanchen2251
链接：https://juejin.im/post/5b55660ee51d4519202e2003
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1 public class Main {
2
3 public static void printArr(int[] arr) {
4 for(int i = 0;i<arr.length;i++){
5 System.out.print(arr[i]+" ");
6 }
7 }
8
9
10 public static int partition(int [] array,int left,int right){
11 //查找一个基数
12 int temp = array[left];
13
14 while(left<right){
15 //从右向左查找小于 基数的下标
16 while(temp<=array[right]&&right>left){
17 right--;
18 }
19 //查找到右边的数字小于基数
20 if(left<right)
21 {
22 array[left] = array[right];
23 left++;
24 }
25 //开始从左向右查找填坑
26 while(temp>=array[left]&&left<right){
27 left++;
28 }
29 //从左边的数组去填右边的坑
30 if(left<right)
31 {
32 array[right]=array[left];
33 right--;
34 }
35 }
36 array[left] = temp;
37 return left;
38
39 }
40
41
42 private static void quickSort(int[] array,int left,int right){
43
44 //设置递归调用边界 如果数组为空数组 就是递归边界 如果数组中元素只有一个也是递归边界
45 //如果 左边的下标 等于右边的下标 递归也是结束
46 if(array ==null||left>=right||array.length<=1){
47 return ;
48 }
49
50 int mid = partition(array, left, right);
51 quickSort(array, left, mid);
52 quickSort(array, mid+1, right);
53
54 }
55
56 public static void main(String[] args) {
57 int[] arr = {6, 4, 3, 2, 7, 9, 1, 8, 5};
58 quickSort(arr, 0,arr.length-1);
59 printArr(arr);
60
61
62 }
63 }
作者：nanchen2251
链接：https://juejin.im/post/5b55660ee51d4519202e2003
来源：掘金