算法基础-快速排序

i、j不相邻时，指向同一个下标
i、j相邻时，j 比 i 小

不管是否相邻，最后一次循环的if条件一定是 i>=j 来退出循环，即最后一次的 if(i<j) 不执行

按照 j 来划分,x = a[l + r >> 1]，分为 [ l，j ]、[ j + 1, r ]

按照 i 来划分,x = a[l + r + 1 >> 1]，分为 [ l，i - 1]、[ i, r ]

i 和 j 相互对应的，记住 j 就行

do i++; while(a[i] < x);
会使得 a[l..i-1] <= x, a[i] >= x

do j--; while(a[j] > x);
会使得 a[j+1..r] >= x, a[j] <= x

if(i < j) swap(q[i], q[j]);
会使得 a[l..i] <= x, a[j..r] >= x

j 之前的元素都 <= x，a[ l ... i - 1 ] <= x
j 之后的元素都 >= x，a[ j + 1 ... r ] >= x
循环结束后 a[ l ... j] <= x，a[ j + 1 ... r ] >= x

do while 先自增自减 ，i 从 l - 1 开始， j 从 r + 1 开始

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i ++ )
            a[i] = in.nextInt();

        quick_sort(a, 0, n - 1);

        for (int i = 0; i < n; i ++ )
            System.out.print(a[i] + "　");

    }
    static void quick_sort(int a[],int l, int r) {
        if(l >= r)
            return;
        int i = l - 1, j = r + 1, x = a[l + r >> 1];
        while(i < j) {
            do {
                i ++;
            }while(a[i] < x);
            do {
                j --;
            }while(a[j] > x);
            if(i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }

        }
        quick_sort(a,l,j);
        quick_sort(a,j + 1, r);
    }
}