模板_快速排序_双指针

//
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+6;
int in[N];

void fastpow( int x,int y )
{
    if( x<y )
    {
        int i=x,j=y,tt=in[y];
        while( i<j )
        {
            while( in[i]<=tt && i<j ) i++;
            in[j]=in[i];                        // 左大赋右空
            while( in[j]>=tt && i<j ) j--;
            in[i]=in[j];                        // 右小赋左空
        }
        in[i]=tt;                               // 归位
        fastpow( x,i-1 );
        fastpow( i+1,y );                       // 分治
    }   
}

int main()
{
    int n,i;

    while( cin>>n )
    {
        for( i=0;i<n;i++ ) cin>>in[i];
        fastpow( 0,n-1 );

        for( i=0;i<n;i++ )
        {
            if( i ) cout<<" ";
            cout<<in[i];
        }
        cout<<endl;
    }
    return 0;
}