C++ 桶排序、基数排序、堆排序
桶排序：是一种基于计数的排序算法，工作原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的）
算法思想：1 设置固定数量的空桶 2 把数据放到对应桶中 3 对每个不为空的桶中数据进行排序 4 拼接不为空的桶中数据，得到结果
桶排序是一种组合排序，时间复杂度取决于桶中的具体排序算法。空间复杂度由于采用了额外的空间，最多存储元素便是元素个数，空间复杂度为O(n)
算法的优点：适用于一定范围内的整数或浮点数排序，不需要比较元素之间的大小，因此排序速度较快，桶排序是一种稳定的排序算法
算法的缺点：当数量范围较大时，需要桶数量越多，会消耗较多的内存空间。桶排序是一种线性排序，不适合大规模数据排序。
代码练习 1 对应力扣 根据字符出现频率排序 代码见下
class Solution {#define ArrayType charvector<vector<ArrayType>> bucket;vector<int> count;void bucketSort(ArrayType* a, int n, int max){bucket.clear();count.resize(max);for(int i=0; i<max; ++i){count[i] = 0;}for(int i=0; i < n; ++i){count[a[i]]++;}for(int i=0; i<=n; ++i){bucket.push_back({});}for(int i=0; i<max; ++i){int cnt = count[i];bucket[cnt].push_back(i);}for(int i=0; i<=n; ++i){sort(bucket[i].begin(), bucket[i].end());}}
public:string frequencySort(string s) {int n = s.size();string ret = "";bucketSort((char *)s.c_str(), n, 256);for(int i=n; i>0; --i){for(int j=0; j<bucket[i].size(); ++j){for(int k=0; k<i; ++k){ret += bucket[i][j];}}}return ret;}
};基数排序是一种非比较型排序算法，它根据数字的每一位来进行排序。通常用于整数排序，基数排序的基本思想是通过对所有元素进行若干次“分配”和“收集”操作来实现排序。
算法思想：1 获取待排序元素的最大值，并确定其位数。2 从最低位开始，依次对所有元素进行“分配”和“收集”操作。 3 在每一位上，根据该位上数字的值将元素分配到对应的桶中。 4 对每个桶中的元素进行顺序收集，得到排序后的部分结果。
时间复杂度是：O(d(n+r)) d是数字的位数、n是待排序元素的数量、r是基数
空间复杂度：是用于存储数组
基数排序优点：不需要进行元素间的比较，因此对于一些特定的情况，可以很容易的排序具有固定宽度的数字序列
基数排序缺点：需要额外的空间来存储桶，大型数据集会耗大量存储。对于复杂的数据类型，可能需要其他排序方式
代码练习 1 对应力扣 排序数组，代码见下
class Solution {const int MAXN = 50005;const int MAXT = 7;const int BASE = 10;void RadixSort(vector<int>& a){int n = a.size();int PowOfBase[MAXT];PowOfBase[0] = 1;for(int i = 1; i < MAXT; ++i){PowOfBase[i] = PowOfBase[i-1] * BASE;}int RadixBucket[BASE][MAXN];int RadixBucketTop[BASE];for(int i=0; i<n; ++i){a[i] += PowOfBase[MAXT - 1];}int pos = 0;while(pos < MAXT){memset(RadixBucketTop, 0, sizeof(RadixBucketTop));for(int i=0; i<n; ++i){int rdx = a[i] / PowOfBase[pos] % BASE;RadixBucket[rdx][RadixBucketTop[rdx]++] = a[i];}int top = 0;for(int i=0; i<BASE; ++i){for(int j=0; j<RadixBucketTop[i]; ++j){a[top++] = RadixBucket[i][j];}}pos++;}for(int i=0; i<n; ++i){a[i] -= PowOfBase[MAXT - 1];}}
public:vector<int> sortArray(vector<int>& nums) {RadixSort(nums);return nums;}
};堆排序：
问题描述：a 插入一个值为a的元素 Q 查询最大的元素 D 删除一个最大的元素
二叉堆：O(1)时间获得最大值、O(logn)时间进行元素的删减、利用数组随机访问的特性模拟二叉树、需要数据结构中的二叉树基础。
二叉树的父节点和左右子节点：parent(id) = (id - 1) / 2、left(id) = id * 2 + 1、right(id) = id * 2 + 2
大顶堆的概念：根节点的值大于其他所有节点
元素插入：往数组尾部插入一个元素，对插入的元素，比较它在树形结构中与父节点的大小关系，来决定是否和父节点进行交换
关于堆排序的相关代码分析
子节点相关位置
function lson(idx){
return 2*idx+1;
}
function rson(idx){
return 2*idx+2;
}
父节点的相关位置
function parent(idx){
return (idx-1)/2;
}
大顶堆或小顶堆
function better(a, b){
return a > b;
}
下沉函数
function heapify(heap, heapSize, curr){
lsonid = lson(curr)
rsonid = rson(curr)
optId = curr
if(lsonid < heapSize && better(heap[lsonid], heap[optId])){
optId = lsonid
}
if(rsonid < heapSize && better(heap[lsonid], heap[optId])){
optId = lsonid
}
if(curr != oprId){
swap(heap[curr], heap[optId])
heapify(h, optId)
}
}
建堆
for i->(n/2 to 0)
heapify(array)
堆排序
for i->(n-1 to 0)
swap(array[0], array[i])
heapify(array, i, 0)
代码练习 对应力扣 排序数组 代码见下：
class Solution {#define eleType int#define idType int#define maxn 50000idType lson(idType idx){return idx*2+1;}idType rson(idType idx){return idx*2+2;}idType parent(idType idx){return (idx - 1) / 2;}bool better(eleType a, eleType b){return a > b;}void Heapify(vector<eleType>& heap, int size, eleType curr){idType lsonId = lson(curr);idType rsonId = rson(curr);idType optId = curr;if(lsonId < size && better(heap[lsonId], heap[optId])){optId = lsonId;}if(rsonId < size && better(heap[rsonId], heap[optId])){optId = rsonId;}if(optId != curr){swap(heap[curr], heap[optId]);Heapify(heap, size, optId);}}
public:vector<int> sortArray(vector<int>& nums) {for(int i=nums.size()/2; i>=0; --i){Heapify(nums, nums.size(), i);}for(int i = nums.size()-1; i>=0; --i){swap(nums[0], nums[i]);Heapify(nums, i, 0);}return nums;}
};