快排

#include<iostream>
#include<string.h>
using namespace std;

char s[100000];
void sort(char* begin,char* end);

int main()
{
    while(cin.getline(s,100000))
    {
        sort(s,s+strlen(s)-1);
        cout<<s<<endl;
    }
}

void sort(char* begin,char* end)
{
    if(begin>=end) return;

    char* head=begin;
    char* tear=end;
    char key=begin[0];

    while(begin<end)
    {
        while(begin<end&&*end>=key)
        {
            end--;
        }
        *begin=*end;

        while(begin<end&&*begin<=key)
        {
            begin++;
        }
        *end =*begin ;
    }
    begin[0]=key;
    sort(head,begin-1);
    sort(end+1,tear);
}