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;
}
};