快速排序，快排的一次分解及递归完整快排

本篇讲解的是Lomuto快排的一个衍生算法，就是基准数取的是数组的第一个元素

首先是快排中的一次执行过程的理解，本次取的是最初的一次，将数组的第一个元素【4】放置到它该去的位置

 1 import java.util.Arrays;
 2 
 3 public class DemoTest {
 4     public static void main(String[] args) {
 5         int[] arr = {4, 10, 2, 4, 9, 3, 1, 7, 5, 6, 8};
 6         //int[] arr = {3, 1, 2, 4, 4, 9, 10, 7, 5, 6, 8};
 7         //int[] arr={2, 1, 3, 4, 4, 9, 10, 7, 5, 6, 8};
 8         quickSort(arr);
 9         System.out.println(Arrays.toString(arr));
10     }
11 
12     public static void quickSort(int[] arr) {
13         int flagNum = arr[0];//第一次排序的时候，需要被放到正确位置的元素
14         int leftPoint = 0;//左边的指针
15         int rightPoint = arr.length - 1;//右边的指针
16         int temp;//交换用的标量
17 
18         while (leftPoint <rightPoint) {
19 
20             //将下面的步骤进行循环，最终将所有数字形成左边比flagNum小，右边
21             //比flagNum大的情况
22             /*注意点：右边的指针要比左边的指针先启动，因为如果左边走到最后一个大于
23             flagNum的时候，rightPoint还要--，这样righPoint就会突破到小的那边
24             因为到最后还是要把flagNum换到指针最终停下的位置，所以右指针侵入到左指针
25             的区域是没事，因为交换之后也是左小右大的情况；
26             但是如果左指针先启动，那么最后就会侵入右指针的区域，结果就是进行flagNum交换
27             的时候会把一个比arr[0]大的数字交换到数组首位置，整个排序过程就失败了*/
28 
29             //右边的指针从右往左找比flagNum小的数字，找到以后停下等待
30             while (arr[rightPoint] >= flagNum && leftPoint < rightPoint) {
31                 rightPoint--;
32             }
33             //leftPoint < rightPoint为了防止，最左边是最小，或者最右边是最大的极端情况
34             // 而造成的索引越界
35             //左边的指针从左向右找比flagNum大的数字，找到以后停下等待
36             while (arr[leftPoint] <= flagNum && leftPoint < rightPoint) {
37                 //leftPoint < rightPoint 要防止右指针侵入左侧区域后，左指针在检索到
38                 //最后一个小于等于arr[0]的元素时，leftPoint++后，把右指针越过去，越过去
39                 //之后感觉还要交换指针，处理的复杂度会上升好几个难度
40                 leftPoint++;
41             }
42 
43             //找到的两个数字交换位置
44             temp = arr[rightPoint];
45             arr[rightPoint] = arr[leftPoint];
46             arr[leftPoint] = temp;
47         }
48 
49         //交换flagNum和leftPoint,这里leftPoint或者rightPoint都可以,因为此时已经重合了
50         temp=arr[0];
51         arr[0]=arr[leftPoint];
52         arr[leftPoint]=temp;
53     }
54 
55 }

下面是完整的快速排序算法理解，主要分析了里面各个步骤的意义

 1 import java.util.Arrays;
 2 
 3 public class DemoQuickSort {
 4     public static void main(String[] args) {
 5         int[] arr = {4, 10, 2, 4, 9, 3, 1, 7, 5, 6, 8};
 6         quickSort(arr, 0, arr.length - 1);
 7         System.out.println(Arrays.toString(arr));
 8 
 9     }
10 
11     public static void quickSort(int[] arr, int arr_left, int arr_right) {
12         int flagNum = arr[arr_left];//第一次排序的时候，需要被放到正确位置的元素
13         int leftPoint = arr_left;//左边的指针
14         int rightPoint = arr_right;//右边的指针
15         int temp;//交换用的标量
16         //if (arr_left == arr_right)
17             //这里如果只用==是无法做到趋近出口的，以本例来讲，左半部分的递归到倒数第二次的
18             //时候，左右指针的索引值都是1，此时请注意看最下面的右半部分的递归调用，rightPoint
19             // =leftPoint=1,arr_right=1,这就造成函数左边
20             //指针的索引值是2，右边指针的索引值是1，左边大于右边了，此时递归无法结束，造成
21             //栈内存溢出。
22         if (arr_left >= arr_right)
23             return;
24         while (leftPoint < rightPoint) {
25 
26             while (arr[rightPoint] >= flagNum && leftPoint < rightPoint) {
27                 rightPoint--;
28             }
29 
30             while (arr[leftPoint] <= flagNum && leftPoint < rightPoint) {
31 
32                 leftPoint++;
33             }
34             temp = arr[rightPoint];
35             arr[rightPoint] = arr[leftPoint];
36             arr[leftPoint] = temp;
37         }
38 
39 
40         temp = arr[arr_left];
41         arr[arr_left] = arr[leftPoint];
42         arr[leftPoint] = temp;
43         quickSort(arr, arr_left, leftPoint - 1);//左半部分的数组递归调用该方法
44         quickSort(arr, rightPoint + 1, arr_right);//右半部分的数组递归调用该方法
45 
46     }
47 }