/*
* @Author: hzf
* @Date: 2020-02-29 20:47:49
* @Last Modified by: hzf
* @Last Modified time: 2020-02-29 21:36:01
*/
/*
桶排序
原理：
准备有限个桶，将一系列数字分批次，按照要求放入桶内，再按照顺序取出
根据数组中的最大数的位数确定取放几次，根据个位、十位、百位上面的数字确定放入哪个桶中
举例： 001 012 022 016 123 1236
最大值为1234，有四位，所以确定取放四次
准备六个桶，分别编号为0 1 2 3 4 5
第一轮根据个位数放置001进入一号桶，012进入二号桶，022进入二号桶，016进入六号桶
123 进入三号桶，1236进入六号桶，结果如下：
一号桶：0001
二号桶：0012 0022
三号桶：0123
六号桶：0016 1236
再依次取出，结果为： 001 012 022 123 016 1236
第二次根据十位数字同理放置，结果为：
零号桶：001
一号桶：012 016
二号桶：022 123
三号桶：1236
六号桶：
取出后为：001 012 016 022 123 1236
第三次根据百位数字，结果为：
零号桶：001 012 016 022
一号桶：123 1236
二号桶：
三号桶：
六号桶：
取出后为：001 012 016 022 123 1236
第四次根据千位数字，结果为：
零号桶：0001 0012 0016 0022 0123
一号桶：1236
二号桶：
三号桶：
六号桶：
取出后为：1 12 16 22 123 1236
*/
#include <iostream>
#include <math.h>
using namespace std;
int GetLength(int *arr)
{
return (sizeof(arr)/sizeof(arr[0]));
}
int maxbits(int *arr)
{
int length = GetLength(arr);
int maxValue = -1;
for (int i = 0; i < length; ++i)
{
if(arr[i] > maxValue)
maxValue = arr[i];
}
int res = 0;
while(maxValue != 0)
{
res += 1;
maxValue /= 10;
}
return res;
}
/*获取数字的第i位置上的数字*/
int getDigit(int num, int i)
{
return (num/pow(10, i - 1) % 10);
}
/*
begin,end 表示排序范围
digit表示取放次数
*/
void radixSort(int *arr, int begin, int end, int digit)
{
const int radix = 10;//基底
int i=0, j=0;
int *bucket = new int[end-begin+1];
for (int d=0; d<digit; d++)
{
/*
count[0] 表示：当前位置（d）是0的数字有多少个
count[1] 表示：当前位置（d）是0 1的数字有多少个
count[2] 表示：当前位置（d）是0 1 2的数字有多少个
count[3] 表示：当前位置（d）是0 1 2 3的数字有多少个
……
*/
int *count = new int[radix];//count[0……9]
for (i=begin; i<=end; ++i)
{
j = getDigit(arr[i], d);//获取数字的第d位置上的值
count[j]++;//对应的桶的容量加一
}
for (i = 1; i < radix; ++i)
{
count[i] += count[i - 1];//计算前缀和,即第i位置上数字是<=i的总个数
}
for (int i = end; i >= begin; ++i)
{
/*
假定这是第一次遍历，那么就是个位数字
从右向左开始，根据当前位置arr[i]的个位数是x，查找count[x]，那么arr[i]就应该排在第x-1位置
为什么？因为小于等于x的数字共有count[x]个，该数字又是在最右边，所以是最后一个放进去，也是最后一个取出的
之后，help[count[x]-1] = arr[i], count[x]-1,下一个（--i）数字
*/
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (int i = begin; i <= end; ++i)
{
/*相当于该轮结束，数字再依次放回，进行下一轮筛选*/
arr[i] = bucket[j];
}
}
}
void radixSort(int *arr)
{
if(arr == NULL || GetLength(arr) < 2)
return;
radixSort(arr, 0, GetLength(arr)-1, maxbits(arr));
}
int main(int argc, char const *argv[])
{
/* code */
return 0;
}
| 
转播
