AcWing 785. Quick sort (template)

Activities - AcWing

【 Quick line up 】 Divide and conquer thoughts

（1） Define the boundary x：q[l], q[(l + r) / 2], Random （ Better choose the middle ）

（2） Adjustment interval ： Less than or equal to x,x, Greater than x

（3） Recursively handle the left and right ends ：

Average complexity O(nlogn), The worst O(n^2), Unstable sequencing

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();
    }

}