本文共 2051 字，大约阅读时间需要 6 分钟。

题目： 对D，a，F，B，c，A，z这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在中间，数字放在最后，不用排序算法，又该怎么解决呢？

思路：

1. 先扫描一遍数组，计算3种类型的元素个数，计算出每个类型的起始下标
2. 扫描一遍，分别写入该去的 “桶” ，再写回原数组，O(n)复杂度

桶排序参考：

/** * @description: 分离开大小写字符，但不改变相对顺序（桶排序思想） * @author: michael ming * @date: 2019/4/13 18:25 * @modified by:  */#include 
   
    #include 
    
     using namespace std;void randomABCandNum(char *ch, size_t N)    //生成随机大小字母和数字{
       char tempch[26+26+10];    int i, j, k, randIndex;    for(i = 0; i < 26; )        tempch[i++] = 'A' + i;    for(j=0; j < 26; j++)        tempch[i++] = 'a' + j;    for(k=0; k < 10; k++)        tempch[i++] = '0' + k;    srand((unsigned)time(NULL));    for(int x = 0; x < N; ++x)    {
           randIndex = rand()%62;        ch[x] = tempch[randIndex];        cout << ch[x] << " ";    }    cout << endl;}void countseparate(char *ch, size_t N){
       size_t lowerNum = 0, upNum = 0, digitNum = 0;    for(int i = 0; i < N; ++i)  //计数，看每种类型有多少个    {
           if(ch[i] >= 'a' && ch[i] <= 'z')            lowerNum++;        else if(ch[i] >= 'A' && ch[i] <= 'Z')            upNum++;        else            digitNum++;    }    size_t lowerIndex = 0, upIndex = lowerNum, digitIndex = lowerNum+upNum;//每种类型的起始下标    int *temp = new int [N];    for(int i = 0; i < N; ++i)  //按区间写入    {
           if(ch[i] >= 'a' && ch[i] <= 'z')            temp[lowerIndex++] = ch[i];        else if(ch[i] >= 'A' && ch[i] <= 'Z')            temp[upIndex++] = ch[i];        else            temp[digitIndex++] = ch[i];    }    for(int i = 0; i < N; ++i)    {
           ch[i] = temp[i];  //写回原数组    }    delete [] temp;    temp = NULL;}void printArr(char* arr, size_t N)  //打印字符数组{
       for(int i = 0; i < N; ++i)    {
           cout << arr[i] << " ";    }    cout << endl;}int main(){
       cout << "请输入N，程序生成大小写字母和数字的组合随机序列：";    size_t N;    cin >> N;    char ch[N];    randomABCandNum(ch, N);    cout << "程序现将字符按[小写字母][大写字母][数字]排列，内部顺序不变：" << endl;    countseparate(ch, N);    printArr(ch, N);}
    
   

转载地址：https://michael.blog.csdn.net/article/details/89288399 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！