一个字符串，包含大小写和空格
使小写在最前面，大写在最后面，字符相对顺序不变
给出占用内存最少，时间复杂度最低的算法？

用快速排序，分为三部分，一部分是小于Z的部分，一部分是小于z的部分还有一部分就是空格！

这样会打乱字母的相对顺序啊~

stl

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

class list{              //这是一个队列，用来存放字符
public:
    char ch;
    list *next;
    list()
    {
        next=NULL;
    }
};
void printA(list *tpp)
{
    for(list *pp=tpp->next;pp;pp=pp->next)
        cout<<pp->ch;
    cout<<endl;
}
void main()
{
    list *tpp,*tpp1,*temp11;
    char *a="asdDGJHfggfDDS dSDFFGDSsS";
    int i=1;
    list *tp=new list;          //一个队列，用来存放小写
    tp->ch='a';
    tpp=tp;
    list *tp1=new list;         //一个队列，用来存放大写
    tp1->ch='A';
    tpp1=tp1;
    while(a[i]!='\0')
    {
        if(a[i]>=97&&a[i]<=128)
        {
            list *temp1=new list;
            temp1->ch=a[i];
            tp->next=temp1;
            tp=temp1;
        }
        if(a[i]>=65&&a[i]<=96)
        {
            list *temp2=new list;
            temp2->ch=a[i];
            tp1->next=temp2;
            tp1=temp2;
        }
        i++;
    }
    tp->next=tpp1->next;           //把两个队列连起来
    list *temp2=new list;
    temp2->ch='\0';
    temp2->next=NULL;
    printA(tpp);
}

占用内存最少吗？

我把我写的发上来。我在想有没有在快点的算法。。。。。


void onSite(char pszArr[])
{
    int left = 1;
    int right = strlen(pszArr) - 1;
    int cnt;
    bool flag;
    do
    {
        flag = false;
        //小写字母往前
        for (int i = right; i >= left; i--)
        {
            if ((pszArr[i] & 96) == 96 && (pszArr[i-1] & 96) != 96)
            {
                char tmp;
                tmp = pszArr[i];
                pszArr[i] = pszArr[i - 1];
                pszArr[i - 1] = tmp;
                cnt = i;
                flag = true;
            }
            if (!flag)
            {
                cnt = left;
            }

        }
        left = cnt + 1;
        
        //大写字母往后
        for (i = left; i <= right; i++)
        {
            if ((pszArr[i] & 96) != 64 && (pszArr[i-1] & 96) == 64)
            {
                char tmp;
                tmp = pszArr[i];
                pszArr[i] = pszArr[i - 1];
                pszArr[i - 1] = tmp;
                cnt = i;
            }
        }
        right = cnt - 1;
    } while (left < right);
}