性时间排序-计数排序、基数排序和桶排序详解与编程实现 (二)

//基数排序
//《算法导论（第二版）》P100 8.3 基数排序
//Author：江南烟雨
//E-Mail:xiajunhust@gmail.com

#include
#include
#include

using namespace std;

//得到某个整数第i位的数值
int getDigitNun(int a,int digit);
//按位排序
void DigitSort(int *a,int n,int digit,int *result);
//基数排序算法
void RadixSort(int *a,int n,int d);

int main()
{
int n = 7,i;
int *a = new int[n];
srand(time(NULL));
for(i = 0;i < n;++i)
*(a + i) = rand();
//判断最大的数的位数
int MaxVal = -1,d = 0;
cout << "Before sort : " << endl;
for(i = 0;i < n;++i)
{
cout << *(a + i) << " ";
MaxVal = MaxVal < *(a + i) *(a + i) : MaxVal;
}
cout << endl;
while(MaxVal > 0)
{
++d;
MaxVal /= 10;
}

RadixSort(a,n,d);

cout << "After sort : " << endl;
for(i = 0;i < n;++i)
cout << *(a + i) << " ";
cout << endl;
}

//基数排序算法
void RadixSort(int *a,int n,int d)
{
int *result = new int[n + 5];
//循环执行按位排序操作
for (int i =1;i <= d;++i)
{
DigitSort(a,n,i,result);
for (int j = 0;j < n;++j)
{
*(a + j) = *(result + j + 1);
}
}

delete[] result;
}

//得到某个整数第i位的数值
int getDigitNun(int a,int digit)
{
while(--digit)
{
a /= 10;
}

return a % 10;
}

//按位排序
//这里采用选择排序
void DigitSort(int *a,int n,int digit,int *result)
{
//记录中间结果
const int num = 15;
int *tempResult = new int[num];
for(int i = 0;i < num;++i)
*(tempResult + i) = 0;//初始化

//tempResult[i]记录数组中等于i的数的个数
for(int i = 0;i < n;++i)
*(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1;

//tempResult[i]记录数组中小于等于i的数的个数
for(int i = 1;i < num;++i)
*(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);

//将个元素直接放入正确的位置
for(int i = n - 1;i >= 0;--i)
{
*(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i);
*(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1;
}

delete[] tempResult;
}

时间复杂度和空间复杂度分析
给定n个d位数，每一个数位可能取值中数是k，如果所用的稳定的按位排序时间复杂度是Θ(n+k)，基数排序时间复杂度是Θ(d(n+k))。空间复杂度O(n+k)。

当d为常数，k=O(n)时，基数排序有线性时间复杂度。

关于如何将每个关键字分解成若干数位方面，有另外一个定理：

给定n个b维数和任何正整数r<=b，基数排序能在Θ((b/r)(n+2^r))时间内对这些数进行排序。

这里，对一个值r<=b，将每个关键字看做是有d = floor(b/r)个数字，每个数字含有r位，再进行计数排序。

上述式子可以推导得到Θ(n)复杂度。

但是这并不意味着基数排序比基于比较的排序算法比如快排更好！因为隐含在记号中的常数因子是不同的。哪一个排序算法更好取决于底层机器的实现特性，比如快排同==排通常可以更有效地利用硬件缓存。同时还取决于输入数据。而且利用计数排序作为中间稳定排序不是原地排序。

桶排序
当输入数据符合均匀分布时，即可以以线性期望时间运行。即使输入不满足线性关系，桶排序也仍然可以以线性时间运行。只要输入满足这样一个性质，即各个桶尺寸的平方和与总的元素数呈线性关系。

桶排序的思想：

将区间[0,1)分成n个相同大小的子区间，或称为桶。然后将n个输入元素分布到各个桶中去。每个桶中的元素用一个链表来存储。

编程实现（CPP）

[cpp]
//桶排序
//《算法导论（第二版）》P102 8.4 桶排序
//Author：江南烟雨（2013-03027）
//E-Mail:xiajunhust@gmail.com

#include
#include
#include
#include

using namespace std;

//桶中链表节点数据结构
typedef struct StructLinkNode{
double elem;
struct StructLinkNode *