LeetCode刷题笔记排序算法桶排序

编程入门行业动态更新时间:2024-10-20 09:31:14

桶排序简介

桶排序、计数排序、计数排序，这三种排序算法的时间复杂度都是线性的，它们之所以能够做到线性的时间复杂度，主要原因是这几个算法是非基于比较的排序算法，不涉及元素之间的比较操作。

这几种排序算法的时间复杂度虽然低，但是对要排序的数据要求比较苛刻，所以关键是要知道这些排序算法的适用场景。

算法思想：

通排序，顾名思义就是为一个值设立一个桶，将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶排序完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

例如[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 个高频元素

给定一个整数数组 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_t = 0;for(const auto num:nums){max_t = max(max_t,++counts[num]);}// 桶中记录相同出现频数的元素vector<vector<int>> buckets(max_t+1);for(const auto count:counts){buckets[count.second].push_back(count.first);}// 从高到低输出出现频率高的元素vector<int> ans;for(int i=max_t; i>=0 && ans.size()<k; --i){for(const auto num:buckets[i]){ans.push_back(num);if(ans.size()==k){break;}}}return ans;}
};

451 根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

输入一个字符串，输出一个按字符出现频率排列的字符串

输入: “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_t = 0;for(const auto ch:s){max_t = max(max_t,++counts[ch]);}// 桶中记录相同出现频数的元素vector<vector<char>> buckets(max_t+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 t = i;while(t > 0){ans += ch;--t;}}}return ans;}
};