AcWing 785. 快速排序（模板）

活动 - AcWing

【快排】分治思想

（1）确定边界x：q[l], q[(l + r) / 2], 随机（最好选中间）

（2）调整区间：小于等于x，x，大于x

（3）递归处理左右两端：

平均复杂度O(nlogn)，最坏O(n^2)，不稳定的排序

import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {

    static int n;
    static int[] arr;
    static StreamTokenizer st;

    static int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }

    static void quickSort(int l, int r){
        if(l >= r) return;
        int i = l, j = r, pivot = arr[(l + r) >>> 1];
        while(i <= j){
            while(arr[j] > pivot) j--;
            while(arr[i] < pivot) i++;
            if(i <= j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i++; j--;
            }
        }
        quickSort(l, j);
        quickSort(i, r);
    }

    public static void main(String[] args) throws Exception{
        PrintWriter pw = new PrintWriter(System.out);
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        n = nextInt();
        arr = new int[n];
        for(var i = 0; i < n; i++) arr[i] = nextInt();
        quickSort(0, n - 1);
        for(var x: arr){
            pw.print(x);
            pw.print(" ");
        }
        pw.flush();
    }

}