前言

  上文写到了快速排序的前置知识：荷兰旗问题，这里开始正式学习快速排序。

😊初始快速排序👇

  假设我有这样一个数组，以数组的末尾值X作为划分的值，小于X的放在数组的左边，大于X的放在数组的右边。这样的话X处于中间位置对于整个数组来说X有序了，X就不用动了，然后继续这样操作左组和右组，每次操作，都会有固定的值处于中间位置排好序，这样只要完成这个递归就可以完成对数组的排序了。

image.png

  这样的话基于荷兰旗问题，每次排序之后，我只要得到等于X的左右下标，就可以基于这个下标，继续递归操作左右数组。

image.png

🤔代码思路👇

• 我需要一个荷兰旗操作的方法，返回等于X的下标数组dx

• 我需要一个递归方法

  • 左组以L到dx[0]-1
  • 右组以dx[1]+1到R
  • 注意递归结束条件，L>=R

❤️代码实现👇

    /**
     * 快速排序入口
     * @param arr
     */
    public static void kspxrk(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        kspx(arr, 0, arr.length - 1);
    }

    /**
     * 递归实现
     * @param arr
     * @param L
     * @param R
     */
    public static void kspx(int[]arr,int L,int R) {
        //考虑递归结束条件
        if(L>=R) {
            return;
        }
        int[] dx = hlqcz(arr, L, R);
        kspx(arr, L, dx[0]-1);
        kspx(arr, dx[1]+1, R);
    }

    /**
     * 荷兰旗问题操作
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int[] hlqcz(int[] arr , int L ,int R ) {
        // L大于R 的时候，越界了
        if(L>R) {
            return new int[] {-1,-1};
        }
        //L == R 的时候，左边结束，右边也结束了
        if(L==R) {
            return new int[] {L,R};
        }
        //左边界
        int less = L - 1;
        //右边界
        int more = R;
        //当前下标,从左开始
        int index = L;
        //当前下标，碰触右边界结束
        while (index<more) {
            if(arr[index]==arr[R]) {
                //如果当前值 和 最右位置值相等，最右位置值作为划分值，当前下标+1，数据不动
                index++;
            }else if(arr[index]<arr[R]) {
                //如果当前值 小于 划分值，当前值和左边界+1的值交换，然后左边界+1，当前下标+1
                swap(arr, index++, ++less);
            }else {
                //如果当前值 大于 划分值，当前值和右边界-1的值交换，然后有边界-1，当前下标不动
                swap(arr, index, --more);
            }
        }
        //当前下标碰到右边界了
        //当前位置的值和R位置的值进行交换，R位置的值是划分值，也就是说它一定在中间
        swap(arr, more, R);
        //返回中间的值的下标
        return new int[] {less+1,more};
    }

    /**
     * 数组的l位置的数 和 R位置的数，交换
     * @param arr
     * @param l
     * @param r
     */
    public static void swap (int[] arr,int l ,int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }

🤔快速排序进阶--随机快排👇

  上面我们用到的数组，用最右侧的数作为划分值，那么就有极端值，最右侧值最大或最小，以及刚好是中间，复杂度分别是O(N^2) 和O（N*logN）,那么为了减少复杂度，就有了随机快排，也就是我随机选一个值，放在最右侧作为划分值。

❤️代码实现👇

    /**
     * 随机快排
     * @param arr
     * @param L
     * @param R
     */
    public static void kspxrk2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        //L-R区间随机一个位置的数和R位置的数交换
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = hlqcz(arr, L, R);
        kspx(arr, L, equalArea[0] - 1);
        kspx(arr, equalArea[1] + 1, R);
    }