一. 题目

二. 思路

三. 代码

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class Main
{
    static final int N = (int) 1e5 + 10;
    static final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] rs;

    int n;
    int[] a = new int[N];

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.work();
    }

    void quickSort(int l, int r)
    {
        if (l >= r) return;
        int mi = rnd.nextInt(l, r + 1), mv = a[mi];
        a[mi] = a[r];//将尾部值放到选定基准的位置，尾部为空

        int i = l, j = r;
        while (i < j)
        {//内部两个循环，每次只有一个在移动，所以最终i==j, 且在空位置相遇
            while (a[i] <= mv && i < j) ++i;
            a[j] = a[i];
            while (a[j] > mv && i < j) --j;
            a[i] = a[j];
        }
        a[i] = mv;//基准元素归位

        quickSort(l, i - 1);
        quickSort(i + 1, r);
    }

    void work() throws Exception
    {
        //读入数据
        rs = br.readLine().split(" ");
        n = Integer.parseInt(rs[0]);
        rs = br.readLine().split(" ");
        for (int i = 0; i < n; ++i)
            a[i] = Integer.parseInt(rs[i]);

        quickSort(0, n - 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i)
            sb.append(a[i]).append(" ");
        bw.write(sb.toString());
        bw.close();
    }
}