#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5 * 1e4;
int n;
int a[N];

void bubble_sort()  //冒泡排序
{
    // for(int i = n - 1; i >= 0; i--) //把最大的往下沉
    // {    
    //     bool flag = false;
    //     for(int j = 0; j < i; j++)
    //         if(a[j] > a[j+1])
    //         {    swap(a[j], a[j+1]); 
    //             flag = true; } 
    //     if(!flag) break; //优化
    // }
    for(int i = 0; i < n; i++)
    {
        bool flag = false;
        for(int j = n-1; j >= i; j--)   //最小的从底网上冒
            if(a[j-1] > a[j])
            {    swap(a[j-1], a[j]);
                flag = true;}
        if(!flag) break;
    }
}

void select_sort()  //选择排序
{
    for(int i = 0; i < n; i++)  
    {
        int k = i;
        for(int j = i+1; j < n; j++)  
            if(a[k] > a[j])
                k = j;          //把小的选上

         if(i != k)  //找到了最小值
            swap(a[i], a[k]);   //每轮交换一次
    }
}

void insert_sort()//直接插入排序，把数插入一个已经排好序的序列
{
    for(int i = 1; i < n; i++)
    {   
        int t = a[i], j;   //先存下来
        for(j = i-1; j >= 0; j--)
            if(a[j] > t)
                a[j+1] = a[j];
            else break;
        a[j+1] = t;
    }
    // for(int i = 1; i < n; i++)
    // {
    //     int t = a[i], j;
    //     for(j = i-1; a[j] > t; j--)
    //         a[j+1] = a[j];  //比t大的往后放，排好序
    //     a[j+1] = t;         //把t放到 大于t的已排序的前面
    // }
}

//快排和归并
void quick_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int i = l, j = r, mid = a[(l+r) >> 1];

    while(i < j)
    {
        while(a[i] < mid) i++;
        while(a[j] > mid) j--;
        if(i < j) swap(a[i], a[j]);
        // else break;
    }
    quick_sort(a, l, j); quick_sort(a, j+1, r);
}

void merge_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid); 
    merge_sort(a, mid+1, r);

    static vector<int> tmp(r);//静态数组，调用快点
    tmp.clear(); //存放临时最小的，然后清空，tmp也可作为全局变量放外面

    int k = 0, i = l, j = mid+1;
    while(i <= mid && j <= r)
        if(a[i] > a[j]) 
        {
            tmp[k++] =  a[j++]; 
            res += mid-i +1; //逆序对个数
        }
        else tmp[k++] = a[i++];

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main() 
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];



    for(int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}

补充一个快排的非递归写法，入栈条件为满足递归的条件，即i<j

int Partition(vector<int>& nums, int l, int r) {
    if(nums.empty() || l < 0 || l >= r || r <= 0) return -1; 
    int i = l-1; int j = r+1;
    int mid = nums[(l+r) >> 1];
    while(i < j) {
        do i++;
            while(nums[i] < mid);

        do j--;    
            while(nums[j] > mid);

        if(i < j)
            swap(nums[i], nums[j]);
    }
    return j;
}
void QuickSort(vector<int>& nums, int l, int r){
    if(nums.empty() || l < 0 || l >= r) return;
    stack<int> stk;
    stk.push(l);
    stk.push(r);
    while(stk.size()) {
        int j = stk.top();
        stk.pop();
        int i = stk.top();
        stk.pop();
        if(i < j){
            int pos = Partition(nums, i, j);
            stk.push(i);
            stk.push(pos);

            stk.push(pos+1);
            stk.push(j);
        }
    }
    // int i = l-1; int j = r+1;
    // int mid = nums[(l+r) >> 1];
    // while(i < j) {
    //     do i++; while(nums[i] < mid);
    //     do j--; while(nums[j] > mid);

    //     if(i < j)
    //         swap(nums[i], nums[j]);
    // }
    // QuickSort(nums, l, j);
    // QuickSort(nums, j+1, r);
}