一、大小值分两边-荷兰国旗问题
    image.png
    解法1：
    image.png

    • 基于交换的算法。
    • 给一个L 和 R表示两个区域边界， 不断扩展。
    • 终止条件： 当前索引值 cur 到达 右边界R的时候。

    解法2（左程云解法）: 对于第一问，只用一个边界就可以。
    image.png
    二、在后面的高级班好像用到了这个算法。

    三、快速排序1.0版本
    image.png
    四、快速排序2.0版本，用荷兰国旗问题分成3份
    image.png

    1. /**
    2.  * @author 张伟-算法
    3.  * @version 1.0
    4.  * @date 2021/9/9 2:00 下午
    5.  */
    6. public class T5_QuickSort {
    7.     public static void main(String[] args) {
    8.         int[] arr = {3,2,5,4 ,1,3};
    9.         process(arr , 0 , arr.length-1);
    10.         System.out.println(Arrays.toString(arr));
    11.     }
    12.     public static void process(int[] arr, int i , int j ){
    13.         if(i >= j ) return ;
    14.         /**这地方要注意啊*/
    15.         int mid = i + ((j - i )>>1);
    16.         int[] pivots = dutchFlag(arr ,i ,j , arr[mid]);
    17.         process(arr ,i , pivots[0]);
    18.         process(arr , pivots[1], j);
    19.     }
    20.     public static int[] dutchFlag(int[] arr , int i , int j , int k ){
    21.         int l = i-1;
    22.         int r = j +1;
    23.         int cur = i;
    24.         while(cur < r){
    25.             if(arr[cur]< k){
    26.                 swap(arr , ++l, cur++);
    27.             }
    28.             else if(arr[cur] == k ){
    29.                 cur++;
    30.             }
    31.             else {
    32.                 swap(arr , --r, cur);
    33.             }
    34.         }
    35.         int[] res = new int [2];
    36.         res[0] = l;
    37.         res[1] = r;
    38.         return res;
    39.     }
    40.     public static void swap(int[] arr , int i, int j){
    41.         int temp = arr[i];
    42.         arr[i ] = arr[j];
    43.         arr[j] = temp;
    44.     }
    45. }

    tips：求中间位置的数一定要加括号，移运算符很低。
    /*这地方要注意啊/
    int mid = i + ((j - i )>>1);
    https://blog.csdn.net/GaleZhang/article/details/108443162
    image.png
    五、快速排序3.0版本
    1.0 和 2.0 版本 的 最差都是 N^2;
    mid 通过随机的方法取到

    1. public static int random(int i , int j ){
    2.     return (int)(Math.random() * (j -i +1)) + i;
    3. }
    4. �

    左程云版本
    image.png
    tips：int[] p 保存的是等于区域的左右边界；
    有点小区别，是事先每次选区域的最右边数作为pivot。
    image.png
    空间复杂度，实际就是每个pivot的位置，跟开多少层有关，最差也是N层，如果像3.0中位置基本在中位数位置的时候，同一层左边返回之后，释放了，然后去右边，所以就是logN
    image.png