04桶排序
# 04 桶排序
# 桶排序简介
桶排序、计数排序、计数排序，这三种排序算法的时间复杂度都是线性的，它们之所以能够做到线性的时间复杂度，主要原因是这几个算法是非基于比较的排序算法，不涉及元素之间的比较操作。
这几种排序算法的时间复杂度虽然低，但是对要排序的数据要求比较苛刻，所以关键是要知道这些排序算法的适用场景。
# 桶排序
算法思想：
通排序，顾名思义就是为一个值设立一个桶，将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶排序完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
例如[25,10,14,14,14,25,10]，我们遍历一遍数组可以建立三个桶[25,10,14]，并将相同值的元素放到同一个桶中形成[[25,25],[10,10],[14,14,14]]；然后对三个桶进行排序[10,14,25]，然后依次输出桶中的元素完成排序。
适用场景：
桶排序一般适用于如下场景：
待排序的数据具有易区分的属性，能够容易就能划分成多个桶，并且桶与桶之间有着天然顺序。这样每个桶内数据都排序完之后，桶与桶之间的数据不需要在进行排序。
待排序的数据具有均匀分布的特性，能够在划分到在各个桶之后，桶中的数据量较为均衡。如果数据经过桶的划分之后，出现极端不平衡情况，那桶排序就相当与只对一个桶进行排序，失去了划分的意义，时间复杂度也随之提高。
# 计数排序
算法思想：
计数排序可以看成是桶排序的一种特殊情况，只是桶的大小粒度不一样。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
适用场景：
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
执行样例：
输入：[8,7,9,5,3,6,9]
算法实现：
void countSort(vector<int>& nums) {
map<int,int> buckets;
// 统计每个数出现的次数
for(int i = 0; i < nums.size(); ++i){
if(buckets.count(nums[i])){
buckets[nums[i]]++;
}else{
buckets.insert(make_pair(nums[i],1));
}
}
// 写回数组
int index = 0;
for(const auto bucket:buckets){
int count = bucket.second;
while(count){
nums[index++] = bucket.first;
count--;
}
}
}
# 基数排序
基数排序就是进行多次桶排序，基数排序中根据进制位数字分配桶，然后根据桶的顺序收集，接着在高进制位继续迭代该过程直到最高进制位完成排序。
当然，基数排序也可以根据其他属性用于其他类型的排序，核心思想都是先按低优先级分配收集排序，再按高优先级分配收集排序。
执行样例：
输入：[8,27,19,15,30,6,9]
算法实现：
void radixSort(vector<int> &nums){
// 计算最大位数
int maxOne = *max_element(nums.begin(),nums.end());
int bit = 1;
while(maxOne>=10){
maxOne /= 10;
++bit;
}
// 创建十个桶
vector<queue<int>> buckets(10);
// 多次桶排序
for(int m=0;m<bit;++m){
// 分配 一次遍历将根据对应位的数值放到对应桶中
for(int i=0;i<nums.size();++i){
int tmp = nums[i];
for(int j=0;j<m;++j){
tmp/=10;
}
buckets[tmp%10].push(nums[i]);
}
// 情况原数组内容
nums.clear();
// 收集 根据桶的顺序收集桶中的元素
for(int i=0;i<10;++i){
while(!buckets[i].empty()){
nums.push_back(buckets[i].front());
buckets[i].pop();
}
}
}
}
# 347 前 K 个高频元素 (opens new window)
给定一个整数数组 nums 和一个整数 k ，返回其中出现频率前 k 高的元素。
输入是一个数组和一个目标值 k，输出是一个长度为 k 的数组
输入: nums = [4,4,4,5,5,6], k = 2 输出: [4,5]
解析：
本题可以使用桶排序，根据元素的频次进行划分。针对样例来说，我们先通过桶排序得到三个桶 [4,5,6]，它们的值分别为 [3,2,1]，表示每个数字出现的次数。
接着，我们对桶的频次进行排序，前 k 大个桶即是前 k 个频繁的数。这里我们可以使用各种排序算法，甚至可以再进行一次桶排序，把每个旧桶根据频次放在不同的新桶内。
针对样例来说，因为目前最大的频次是 3，我们建立 [1,2,3] 三个新桶，它们分别放入的旧桶为 [[6],[5],[4]]，表示不同数字出现的频率。最后，我们从后往前遍历，直到找到 k 个旧桶。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计元素出现频数
unordered_map<int,int> counts;
int max_cnt = 0;
for(const auto num:nums){
max_cnt = max(max_cnt,++counts[num]);
}
// 桶中记录相同出现频数的元素
vector<vector<int>> buckets(max_cnt+1);
for(const auto count:counts){
buckets[count.second].push_back(count.first);
}
// 从高到低输出出现频率高的元素
vector<int> ans;
for(int i=max_cnt; i>=0 && ans.size()<k; --i){
for(const auto num:buckets[i]){
ans.push_back(num);
if(ans.size()==k){
break;
}
}
}
return ans;
}
};
# 451 根据字符出现频率排序 (opens new window)
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
输入一个字符串，输出一个按字符出现频率排列的字符串
输入: "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。注意'A'和'a'被认为是两种不同的字符。
解析：
本题可以使用桶排序，根据元素的频次进行划分。针对样例来说，我们先通过桶排序得到三个桶 [A,a,b]，它们的值分别为 [1,1,2]，表示每个数字出现的次数。
接着，我们对桶的频次进行排序，然后根据频次重新拼接字符串。这里我们可以使用各种排序算法，甚至可以再进行一次桶排序，把每个旧桶根据频次放在不同的新桶内。
针对样例来说，因为目前最大的频次是 2，我们建立 [1,2] 两个新桶，它们分别放入的旧桶为 [[A,a],[b]]，表示不同字符出现的频率。最后，我们从后往前遍历，根据频次拼接字符串。
class Solution {
public:
string frequencySort(string s) {
// 统计元素出现频数
unordered_map<char,int> counts;
int max_cnt = 0;
for(const auto ch:s){
max_cnt = max(max_cnt,++counts[ch]);
}
// 桶中记录相同出现频数的元素
vector<vector<char>> buckets(max_cnt+1);
for(const auto count:counts){
buckets[count.second].push_back(count.first);
}
// 根据字符频率重新拼接字符串
string ans = "";
for(int i=buckets.size()-1;i>=0;--i){
for(const auto ch:buckets[i]){
int cnt = i;
while(cnt > 0){
ans += ch;
--cnt;
}
}
}
return ans;
}
};