C++程序对字符的字符串进行排序

给定一个由小写字符’a’ – ‘z’组成的字符串。我们需要编写一个程序，以排序的顺序打印此字符串的字符。
示例：

输入： bbccdefbbaa
输出： aabbbbccdef

输入： geeksforgeeks
输出： eeeefggkkorss

简单方法 是使用快速排序或归并排序等排序算法对输入字符串进行排序并打印它。

// C++程序以对字符的字符串进行排序
#include<bits/stdc++.h>
using namespace std;

//以排序的顺序打印字符串的函数
void sortString(string &str)
{
    sort(str.begin(), str.end());
    cout << str;
}

//驱动程序
int main()
{
    string s = "geeksforgeeks";
    sortString(s);
    return 0;
}

输出：

eeeefggkkorss

时间复杂度： O(n log n) ，其中n是字符串的长度。

空间复杂度： O(1)，因为没有使用额外的空间。

一种 高效的方法 是首先观察到只有 26 种唯一字符。因此，在散列数组中存储从’a’到’z’的所有字符出现的计数。散列数组的第一个索引将表示字符’a’，第二个将表示字符’b’，依此类推。最后，我们将简单地遍历散列数组并按输入字符串中它们出现的次数打印从’a’到’z’的字符。

下面是上述思想的实现:

// C++程序以对字符的字符串进行排序
#include<bits/stdc++.h>
using namespace std;

const int MAX_CHAR = 26;

//以排序的顺序打印字符串的函数
void sortString(string &str)
{
     //散列数组用于保持字符计数。
     //最初，所有字符的计数都初始化为零。
    int charCount[MAX_CHAR] = {0};

     //遍历字符串并递增字符计数
     for (int i=0; i<str.length(); i++)

         // 'a'-'a'将为 0，'b'-'a'将为 1，
         // 因此，对于在计数数组中的字符位置
         // 我们将执行 str [i] - 'a'。
         charCount[str[i]-'a']++;   

     //遍历散列数组并打印字符
     for (int i=0;i<MAX_CHAR;i++)
         for (int j=0;j<charCount[i];j++)
             cout << (char)('a'+i);
}

//驱动程序
int main()
{
    string s = "geeksforgeeks";    
    sortString(s);    
    return 0;
}