排序算法是研究非常广泛且超级经典的算法，主流排序算法的时间复杂度基本都在O(nlogn)。

今天就介绍一种以hash表为基础的，时间复杂度能够达到O(n)的排序算法——计数排序；

同时基于它的思想，完成时间复杂度同样为O(n)的求Top N热词的小功能应用。

算法思想

01 n个数据需要排序，就把数据映射到 [0, n-1] ，然后用 int 数组 id2num [n] 完成 “编号 to 出现次数的映射 ”；

　　简单来说，对于正整数数据，先找到最大值maxData，那么可以直接创建 int data2num [ maxData+1 ]的数组，这样 data2num[i] 就是数据 i 的出现次数。

　　映射和统计出现次数都只需要遍历一遍，时间复杂度均为 O(n)。

02 因为已经完成了data2num的映射，索引是数据，且索引int值的大小顺序与数据的大小顺序一致，所以直接输出即可完成排序；

　　例如原始数据为[1,3,9, 5,7,9]，则data2num数组中索引为[1,3,5,7]的值都是1，data2num[9] = 2，索引为剩下的[0,2,4,6,8]的值都是0；

　　递增排序结果：

　　　　我们直接顺序遍历data2num数组，对每个值data2num[i]，输出data2num[i]个 i 即可。样例的输出就是：[1,3,5,7,9,9]

　　递减排序结果：

　　　　我们直接逆序遍历data2num数组，做同样的操作。样例的输出就是：[9,9,7,5,3,1]

03 显而易见，这种算法适合处理重复值很多的序列，那么它的最佳应用就是求Top N热词。

　　因为Top N热词就是出现次数最多的前N个词，那么我们只需要建立num2string的链表数组即可；

　　这样，num2string[i] 就表示存储了所有出现 i 次的热词string的链表，逆序输出 N 个词就完成了这个任务。

C++代码

#include
#include
#include

using namespace std;

// 计数排序，通过记录所有元素出现的次数来实现O(n)的排序算法
// 以最简单的正整数数据为例：
vector JiShuSort(vector&a, bool asc=true) {
int n = a.size(), maxData = 0;

//找到最大元素（每个元素都是正整数）  
for (int i = 0; i < n; i++) {  
    maxData = max(maxData, a\[i\]);  
}

// 数据都是正整数，最多有从1到maxData共maxData种数据，所以空间只用开辟这么大  
vector<int>data2num(maxData + 1, 0);  
// 记录所有数据出现的次数，进行从maxData种数据到出现次数num的映射 data to num  
for (int i = 0; i < n; i++) {  
    data2num\[a\[i\]\]++;  
}

// 获得排序结果  
vector<int> ans;  
if (asc) {      //递增顺序就从前向后遍历  
    for (int i = 1; i <= maxData; i++) {  
        for (int j = 0; j < data2num\[i\]; j++) {  
            ans.push\_back(i);  
        }  
    }  
}  
else {          //递减顺序就从后向前遍历  
    for (int i = maxData; i > 0; i--) {  
        for (int j = 0; j < data2num\[i\]; j++) {  
            ans.push\_back(i);  
        }  
    }  
}  
return ans;  

}

// 打印n个字符串中出现次数最多的前N个字符串，TOP N 热词算法
// n个字符串共有cnt种不同的字符串
// 时间复杂度O(3*n + 2*cnt + N) = O(n)
void PrintTopN(vector& a, int N) {
cout << "-----------the Top " << N << " hot words is belowe--------------\n"; unordered_map string2id; //hash表对新key值的默认value值为0
int n = a.size(), cnt = 0;
// 对cnt个不同的字符串进行hash映射，映射到[1,cnt]
for (int i = 0; i < n; i++) { if (string2id[a[i]] == 0)string2id[a[i]] = ++cnt; } // 进行id到string的反向映射 vectorid2string(cnt + 1);
for (int i = 0; i < n; i++) {
id2string[string2id[a[i]]] = a[i];
}

// 记录cnt个字符串出现的次数，第i个字符串出现num\[i-1\]次  
vector<int>id2num(cnt + 1);  
for (int i = 0; i < n; i++) {  
    id2num\[string2id\[a\[i\]\]\]++;  
}  
// 找到最大出现次数  
int maxNum = 0;  
for (int i = 1; i <= cnt; i++)  
    maxNum = max(maxNum, id2num\[i\]);

// 记录每个出现次数对应的字符串id  
vector<vector<int>>num2id(maxNum + 1, vector<int>());  
for (int i = 1; i <= cnt; i++) {  
    num2id\[id2num\[i\]\].push\_back(i);  
}

// 逆序打印top N  
for (int i = maxNum; i > 0; i--) {  
    for (int x : num2id\[i\]) {  
        if (N-- == 0)return;  
        cout << id2string\[x\] << '\\n';  
    }  
}  

}

int main() {
string a[11] = { "one","two","three","four","five","six","steven","eight","nine","ten","eleven" };
vector strData;
vector intData;
// 让strData中是1个“one”，2个“two”，…， 11个“eleven”
// 让intData中是1个1，2个2，…，11个11
for (int i = 0; i < 11; i++) { for (int j = 0; j <= i; j++) { strData.push_back(a[i]); intData.push_back(i + 1); } } // 获得intData的递减排序结果 vector ans = JiShuSort(intData, false);
cout << "---------------下面是intData递减排序后的数据---------------\n";
for (int x:ans) {
cout << x << '\n';
}
// 获得intData的递增排序结果，asc默认是true
ans = JiShuSort(intData);
cout << "---------------下面是intData递增排序后的数据---------------\n";
for (int x : ans) {
cout << x << '\n';
}
//打印strData中的top 10 热词
PrintTopN(strData, 10);
return 0;
}