前言：算法系列的文章源代码将陆续更新到github上，其地址如下：
https://github.com/zhaolingxi/AlgorithTtraining
在上一篇文章中，我们介绍的排序算法均是基于比较的排序算法。
上篇导航：算法入门第二节--基础排序算法归纳1
就是说在实现算法的前提是每一个参与排序的元素，必须有一个明确的可以比较的大小关系，或是明确的大小比较规则。
如果是对自定义的类等元素进行比较，需要重载运算符（C++）或者写比较器（java）。ps:比较排序时间复杂度有下限
实例代码如下：
template <typename T>
bool operator < (T t1, T t2)
{
//t1.sortnum<t2T.sortnum;
}
基于比较的排序有一个特征，就是排序总依赖于一个大小关系（抽象或是具体）
而在具体的业务中，我们可能会需要基于性别、基于职业、基于种类的排序。在复杂情况下，使用重载运算符不是一个明智的行为。
所以，我们可以选择另一种排序方式，那就是桶排序。
桶排序仅关心种类，将不同的元素划分进入不同的桶。我们称之为入桶。
然后将同一个桶的元素进行二次分类，将其放到更小的桶里面，我们还是称之为入桶。
最后，我们在需要验证、查询的时候，将不同桶的元素依次取出，我们称之为出桶。
那么桶排序需要哪几个步骤呢？
1.确定桶的数量：可以通过找出最大最小值，除以区间的划分大小确定。也可以通过业务直接确定
2.确定桶的大小：可以通过给出一个小空间，不够用在重新申请拷贝（类似vector），或者使用链表之类的数据结构（排序会稍微麻烦一些）
3.如有必要，进行桶内的排序（随便选取一种排序方式）
进行完这些步骤之后，总的时间复杂度是多少呢？
最大最小n,初始化k，再加上每个桶排序（对每个桶内的元素进行排序。可以选择任意一种排序算法。）
当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。
我们这里提供两个具有桶排序思想的代码实例（基数排序和计数排序）
但需要明确的是，这两种排序并不能代表桶排序，它们只是具有桶排序思想的特例。
基数排序实例：
//桶排序
//时间复杂度：O(n)依赖具体数据与场景
//空间复杂度：O(n)依赖具体数据与场景
//算法稳定度：稳定
//排序思想：利用划分区域的分类方式代替比较分类
//基数排序：
// 以不同元素的区域，划定桶处理的元素范围
// 使用了词频表完成如桶与出桶
bool sort_Bucket(std::vector<int>& ioArray)
{
bool res = false;
if (ioArray.size() < 2) return res;
radixSort(ioArray, 0, ioArray.size()-1, maxbits(ioArray));
res = true;
return res;
}
void radixSort(std::vector<int>& ioArray, int left, int right, int digit)
{
static int radix = 10;
int i = 0, j = 0;
//准备足够的辅助空间
std::vector<int> tempvec(right-left+1);
for (size_t d = 1; d <= digit; d++)
{
//10个空间
//count[0]当前位是零的数
//count[1]当前位是0和1的数
//count[n]当前位是0到n的数
std::vector<int> count(radix);
for (size_t i = left; i <= right; i++)
{
j = getDigit(ioArray[i],d);
count[j]++;
}
for (size_t i = 1; i < radix; i++)
{
count[i] = count[i] + count[i - 1];
}
for (int i = right; i >= left; i--)
{
j = getDigit(ioArray[i], d);
tempvec[count[j] - 1] = ioArray[i];
count[j]--;
}
for (i = left, j = 0; i <= right; i++, j++) {
ioArray[i] = tempvec[j];
}
}
}
int maxbits(std::vector<int>& ioArray)
{
int max = INT_MIN;
for (size_t i = 0; i < ioArray.size(); i++)
{
max = __max(max, ioArray[i]);
}
int res = 0;
while (max != 0)
{
res++;
max = max / 10;
}
return res;
}
int getDigit(int iNum, int d)
{
return ((iNum / (int)pow(10, d - 1)) % 10);
}
计数代码实例：
//桶排序
//时间复杂度：O(n)依赖具体数据与场景
//空间复杂度：O(n)依赖具体数据与场景
//算法稳定度：稳定
//排序思想：利用划分区域的分类方式代替比较分类
//计数排序：
// 对每一个元素可能出现的值进行频率划分
bool sort_Bucket2(std::vector<int>& ioArray)
{
bool res = false;
if (ioArray.size() < 2) return res;
countSort(ioArray, 0, ioArray.size() - 1);
res = true;
return res;
}
void countSort(std::vector<int>& ioArray, int left, int right)
{
int max = INT_MIN;
for (size_t i = left; i < right; i++)
{
max = __max(max, ioArray[i]);
}
std::vector<int> tempvec(max+1);//计数排序的计数是每一个数值都需要一个计数位
for (int i = left; i < right; i++)
{
tempvec[ioArray[i]]++;
}
int i = left;
for (int j = 0; j < tempvec.size(); j++)
{
while (tempvec[j] != 0) //这里要求是不为零数才行，实际使用中把它视为不等于初始值就行
{
ioArray[i++] = j;
}
}
}
Q.E.D.
