1. y总模板（选左边第一个分界，边界为 [l, j] [j + 1, r]）
2. 挖坑法（左边第一个挖掉，左右依次填坑，直到i=j）

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

int A[N];

void quick_sort(int left, int right){
    if(left >= right) return ;
    int i = left - 1, j = right + 1, t = A[left]; // 选左边，就用 [l, j] [j + 1, r]

    while(i < j){
        do{
            i ++;
        }while(A[i] < t);
        do{
            j --;
        }while(A[j] >t);
        if(i < j) swap(A[i], A[j]);
    }

    quick_sort(left, j);
    quick_sort(j + 1, right);
}

void quick_sort_(int left, int right){
    if(left >= right) return ;
    int i = left, j = right, t = A[left];

    while(i < j){
        while(i < j && A[j] >= t) j --;
        A[i] = A[j];
        while(i < j && A[i] <= t) i ++;
        A[j] = A[i];
    }
    A[i] = t;
    quick_sort_(left, i);
    quick_sort_(i + 1, right);
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> A[i];
    }
    quick_sort(0, n - 1);
    for(int i = 0; i < n; i ++){
        cout << A[i] << " ";
    }
    return 0;
}