题解 | #快速排序#

import java.io.*;

public class Main {
    private static final int MAX = 100001;
    private static int n;
    private static int[] arr = new int[MAX];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != in.TT_EOF) {
            n = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            quickSort(0, n - 1);
            for (int i = 0; i < n; i++) {
                out.print(arr[i] + " ");
            }
            out.println();
//            out.flush();
        }
        out.flush();
        out.close();
    }

    public static void quickSort(int l, int r) {
        if (l >= r) {
            return;
        }
        //随机产生一个划分数
        int x = arr[l + (int) (Math.random() * (r - l + 1))];
        int mid = partition1(l, r, x);
        quickSort(l, mid - 1);
        quickSort(mid + 1, r);
    }

    public static int partition1(int l, int r, int x) {
        int a = l, xi = l, i = l;
        while (i <= r) {
            if (arr[i] <= x) {
                swap(a++, i);
                if (arr[a - 1] == x) {
                    xi = a - 1;
                }
                i++;
            } else {
                i++;
            }
        }
        swap(a - 1, xi);
        return a - 1;
    }

    public static void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}