P4660 字符串排序（入门）

解题思路

第一步，读懂题目。 要我们把一个由 a~z 组成的小写字母串，按字母表的顺序重新排好。比如 babcccxyz 排完就变成 abbcccxyz，所有的 b 都排到 c 前面，c 又排到 y、z 前面。

第二步，想一想生活里的例子。 老师发糖果，让我们把同样颜色的一堆糖果按彩虹色顺序排队。我们可以用"数数"的办法代替排序：先数一数字符串里 a 出现几次、b 出现几次……一直到 z，然后从 a 开始，把 a 连续输出它的次数个，再输出 b、c……这样输出的结果天然就是按字母表排序的，一个都不用调换。

第三步，具体怎么做。 开一个长度为 26 的计数器数组 letterCnt，下标 0~25 分别对应 a~z。读入字符串后，对每个字符 str[i]，把 letterCnt[str[i]-'a'] 加 1。最后两层循环：外层从 0 到 25，内层把对应字母输出 letterCnt[i] 次。

第四步，用样例验证。 拿 babcccxyz 来说：a 出现 1 次、b 出现 2 次、c 出现 3 次，x、y、z 各 1 次。从 a 开始一个个倒出来，就得到 abbcccxyz，和样例一致。整个过程我们一次交换都没有做，只是"数数 + 倒出来"。

第五步，理解为什么不用真正"交换"。 比较排序需要两个数比来比去、换来换去；而这道题每个字母只有 26 种可能，我们只要数个数再按顺序倒出来，一次交换都不用做。这就是"计数排序"的思路：把"比较大小"换成了"数数"。当数据种类很少时，这个办法又快又直观，这也告诉我们选择算法要看数据的特点，不是越复杂的算法越好。

第六步，处理边界情况。 字符串长度最长 1000，所以字符数组开 1005 就够了；如果所有字母都一样，比如全是 z，那么只有最后一个计数器是正数，从 a 扫到 y 都不输出，最后把 z 输出一遍，结果也正确。注意输出完要换行。

参考代码

// P4660 字符串排序：统计每个字母出现次数，按字母表顺序输出
#include <iostream>
int main() {
    char str[1005];
    int letterCnt[26] = {0};
    std::cin >> str;
    // 统计 a~z 每个字母出现几次
    for (int i = 0; str[i]; i++) letterCnt[str[i] - 'a']++;
    for (int i = 0; i < 26; i++)
        while (letterCnt[i]--) std::cout << char('a' + i);
    std::cout << "\n";
    return 0;
}

复杂度分析

统计每个字符要遍历一次字符串，需要 O(len) 的时间，len 是字符串长度，最长 1000。最后输出要再枚举 26 个字母并输出 len 个字符，也是 O(len) 级别。总时间复杂度 O(len)，空间上只用了 26 个计数器和一个字符数组，都是常数级别，非常高效。