1. 思路

①确定分界点x，在区间[ l , r ]随意取一个数

②根据分界点x调整，使得x左边的数都小于等于x，x右边的数都大于等于x （难点）

③递归处理左边和右边

2. 代码模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        String[] strs = in.readLine().split(" ");
        for(int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(strs[i]);
        quickly_Sort(arr, 0, arr.length - 1);
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        in.close();
    }

    //a为要排序数组,l为左边界，r为有边界
    public static void quickly_Sort(int[] a, int l, int r) {
            if(l >= r) return;  //如果区间没有数，或者只有一个数
            int x = a[l];       //确定分界点,在区间[ l , r ]随意取一个数
            int i = l - 1, j = r + 1;   //方便后面统一处理
            while(i < j) {
                while(a[++i] < x);      //从左边界开始找到第一个大于等于x的数
                while(a[--j] > x);      //从右边界开始找到第一个小于等于x的数
                if(i < j) {             //如果i >= j 就代表此区间已经排好序，
                                            //否则交换刚才找到的数，调整区间顺序
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
            quickly_Sort(a, l, j);      //递归排序左边区间
            quickly_Sort(a, j + 1, r);  //递归排序右边区间
    }
}

3. 复杂度分析

• 时间复杂度：O(nlogn)

• 空间复杂度：O(logn)

4. 注意

如果递归排序quickly_Sort(a, l, j); quickly_Sort(a, j + 1, r);时，分界点x不能为a[r],还有a[r + l + 1 >> 1].

例如：当a = {1, 2};否则会造成死循环

如果递归排序quickly_Sort(a, l, i - 1); quickly_Sort(a, i, r);时，分界点x不能为a[l],还有a[r + l >> 1].

我记忆的技巧：当递归取i时，不能用左边界当分界点。反之，当递归取j时，不能用右边界当分界点。如果记不住就按模板来就行。