时间复杂度$O(n!)$

(但有些时候还比不上之前的版本)

#include<bits/stdc++.h>
using namespace std;
int a[1001],t[1001],ans[1001],b[1001],n;
void monkey_sort(int l,int r,int step)
{
    if(step==n+1){
        bool s=1;
        for(int i=2;i<=n;i++)
            if(t[i-1]>t[i])s=0;

        if(s)
            for(int i=1;i<=n;i++)ans[i]=t[i];

        return;
    }
    for(int i=1;i<=n;i++)
        if(!b[i]){
            t[step]=a[i];
            b[i]=1;
            monkey_sort(l,r,step+1);
            b[i]=0;
        }

    if(step==1)
        for(int i=1;i<=n;i++)a[i]=ans[i];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    monkey_sort(1,n,1);
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
}