使用sort()与count()按字符频率排序字符串失败的问题排查

嘿，我来帮你拆解一下代码里的问题，其实主要是两个核心原因导致排序结果不对：

1. 排序过程中字符串被修改，count()拿到的是错误的频率 #

你的str是全局变量，而sort()在执行时会不断交换字符串里的字符，实时修改str的内容。但你的cmp函数每次都调用count(str.begin(), str.end(), a)，这里的str已经是被排序修改中的版本了，不是原始字符串的字符频率！

举个例子：排序刚开始时str是原始值，count出的频率是对的，但交换几个字符后，str里的字符分布变了，再调用count就会得到错误的频率数值，排序逻辑自然彻底乱掉。

2. 比较函数不符合C++ sort()的严格弱序要求 #

当两个字符的频率相同时，你的cmp(a,b)和cmp(b,a)都会返回false（因为count(a)等于count(b)，所以>不成立）。但C++的sort()要求比较函数必须满足严格弱序：如果a不小于b，且b不小于a，那么a必须和b等价（比如这里频率相同的情况下，需要额外的排序规则）。违反这个要求会导致sort()行为未定义，出现各种奇怪的输出。

修复方案：先预统计频率，再用合法的比较函数排序 #

解决思路很简单：先一次性统计好原始字符串的字符频率，存在一个容器里，排序时直接用预存的频率；同时给频率相同的字符加上明确的排序规则，满足严格弱序。

这里给你两种实现方式，你可以根据需求选：

方式一：用unordered_map统计频率（通用，适合所有字符类型）

#include "bits/stdc++.h"
using namespace std;

int main() {
    string str = "tetetafseaaaast";
    
    // 第一步：预统计原始字符串的字符频率
    unordered_map<char, int> char_freq;
    for (char c : str) {
        char_freq[c]++;
    }

    // 第二步：自定义排序规则：先按频率降序，频率相同按字符字典序升序
    sort(str.begin(), str.end(), [&char_freq](char a, char b) {
        if (char_freq[a] != char_freq[b]) {
            return char_freq[a] > char_freq[b]; // 频率高的排前面
        } else {
            return a < b; // 频率相同，按字符从小到大排，也可以改成a>b按降序
        }
    });

    cout << str << endl;
    return 0;
}

方式二：用数组统计频率（更快，适合ASCII字符）

如果你的字符串只有ASCII字符，用数组统计会比unordered_map更快：

#include "bits/stdc++.h"
using namespace std;

int main() {
    string str = "tetetafseaaaast";
    
    // 初始化频率数组，ASCII字符范围是0-255
    int char_freq[256] = {0};
    for (char c : str) {
        // 转成unsigned char避免负数索引
        char_freq[(unsigned char)c]++;
    }

    sort(str.begin(), str.end(), [&char_freq](char a, char b) {
        int freq_a = char_freq[(unsigned char)a];
        int freq_b = char_freq[(unsigned char)b];
        if (freq_a != freq_b) {
            return freq_a > freq_b;
        } else {
            return a < b;
        }
    });

    cout << str << endl;
    return 0;
}

用这个代码测试你的例子"tetees"，会得到正确的输出"eeetts"，你的原始字符串也能得到符合预期的排序结果。

备注：内容来源于stack exchange，提问作者Mightlaus