package com.cc;

import java.util.Arrays;

/**
 * @Author: cc
 * @Create: 2021/12/21
 * 快速排序（双边循环）
 * 1、选择最左元素作为基准 点元素
 * 2、j 指针负责从右向左找比基准点小的元素，
 * 3、i 指针负责从左向右找比基准点大的元素,一旦找到二者交换，直至i, j相交
 * 4、最后基准点与i (此时i与j相等)交换, i即为分区位置
 */
public class Quick2 {
    public static void main(String[] args) {
        int [] a = {4,3,6,1,7,9,8,2};
        quick(a, 0, a.length-1);
    }
    private static void quick(int []a,int l,int h){
        if (l >= h){
            return;
        }
        int p = partition(a,l,h);
        quick(a, l , p-1);
        quick(a, p + 1, h);
    }
    private static int partition(int []a,int l, int h){
        int i = l;
        int j = h;
        int pv = a[l]; //基准点为左边第一个
        while (i < j){
            //j从右边找小的,找到后等i找到比基准点大的，然后i和j交换
            while (i < j && pv < a[j]){
                j--;
            }
            //i从左边找大的
            while(i < j && pv >= a[i]){
                i++;
            }
            swap(a, i ,j);
        }
        swap(a,l,i);
        System.out.println(Arrays.toString(a));
        return j;
    }

    private static void swap(int [] a,int i ,int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

输出结果如下：

[1, 3, 2, 4, 7, 9, 8, 6]
[1, 3, 2, 4, 7, 9, 8, 6]
[1, 2, 3, 4, 7, 9, 8, 6]
[1, 2, 3, 4, 6, 7, 8, 9]
[1, 2, 3, 4, 6, 7, 8, 9]