1. 单边快排

1.1 单边快排思路

1.2 代码实现

public class kuai_su_pai_xu {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        quick(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 递归
     */
    private static void quick(int[] a, int low, int high){
        if (low >= high) return;
        int p = partition1(a, low, high);
        quick(a, low, p - 1);//左边分区
        quick(a, p + 1, high);//右边分区
    }

    /**
     * 用于分区  单边循环
     * @param a 目标数组
     * @param low 左指针
     * @param high 右指针
     * @return 返回基准点元素所在的正确索引，用它确定下一轮分区的边界
     */
    private static int partition1(int[] a, int low, int high){
        //1.
        int pv = a[high];
        int i = low;
        int j = low;
        while (j < high){
            //2.
            if (a[j] < pv){
                swap(a, i, j);
                //3.
                i++;//维护小于基准点的边界
            }
            j++;
        }
        //4.
        swap(a, i ,j);
        System.out.println(Arrays.toString(a) + " i ==>" + i);
        //返回值表示了基准点元素所在的正确索引，用它确定下一轮分区的边界
        return i;
    }

    /**
     * 置换函数
     */
    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

简单图解

图解单边快排

运行结果

[3, 2, 1, 4, 9, 8, 7, 5] i ==>3
[1, 2, 3, 4, 9, 8, 7, 5] i ==>0
[1, 2, 3, 4, 9, 8, 7, 5] i ==>2
[1, 2, 3, 4, 5, 8, 7, 9] i ==>4
[1, 2, 3, 4, 5, 8, 7, 9] i ==>7
[1, 2, 3, 4, 5, 7, 8, 9] i ==>5
[1, 2, 3, 4, 5, 7, 8, 9]

2. 双边循环快排

2.1 双边循环快排思路

2.2 代码实现

public class kuai_su_pai_xu {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        quick(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 递归
     */
    private static void quick(int[] a, int low, int high){
        if (low >= high) return;
        int p = partition2(a, low, high);
        quick(a, low, p - 1);//左边分区
        quick(a, p + 1, high);//右边分区
    }

    /**
     *双边
     */
    private static int partition2(int[] a, int low, int high){
        int pv = a[low];
        int i = low;
        int j = high;
        while (i<j){
            //j 从右往左找小的
            //1. 必须先从 j 开始 从右往左
            // 这是因为 如果先从 i 找 i会停止在比基准点大的元素上
            // 同时 j 也会停留在这上面
            // 最后一步就会将 这个比基准点大的元素 移动到基准点上
            while (i < j && a[j] > pv){
                j--;
            }
            //i 从左往右找大的
            //1. 这里加上等于号 是因为 a[i] 的初始值就是 pv 即左侧基准点；不加的则i始终不动
            //2. 加上 i < j 是为了防止后续的序列中已经排好序了 造成i越过了j ；上同
            while (i < j && a[i] <= pv){
                i++;
            }

            swap(a, i , j);
        }
        swap(a, low, i);
        System.out.println(Arrays.toString(a) + " i ==>" + i);
        return i;
    }

    /**
     * 置换函数
     */
    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

运行结果：

[1, 3, 4, 2, 5, 8, 9, 7] i ==>4
[1, 3, 4, 2, 5, 8, 9, 7] i ==>0
[1, 2, 3, 4, 5, 8, 9, 7] i ==>2
[1, 2, 3, 4, 5, 7, 8, 9] i ==>6
[1, 2, 3, 4, 5, 7, 8, 9]