一. 算法描述
基数排序(以整形为例),将整形10进制按每位拆分,然后从低位到高位依次比较各个位。主要分为两个过程:
(1)分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中(比如53,个位为3,则放入3号桶中)
(2)收集,再将放置在0~9号桶中的数据按顺序放到数组中
重复(1)(2)过程,从个位到最高位(比如32位无符号整形最大数4294967296,最高位10位)
以【521 310 72 373 15 546 385 856 187 147】序列为例,具体细节如下图所示:
在数据中最高位为3,进行了三次分配、收集过程后,变成有序数组。
二. 算法分析
平均时间复杂度:O(dn)(d即表示整形的最高位数)
空间复杂度:O(10n) (10表示0~9,用于存储临时的序列)
稳定性:稳定
三. 算法实现
-
-
-
-
-
-
-
int GetNumInPos(int num,int pos)
-
{
-
int temp = 1;
-
for (int i = 0; i < pos - 1; i++)
-
temp *= 10;
-
-
return (num / temp) % 10;
-
}
-
-
-
-
-
-
-
-
#define RADIX_10 10 //整形排序
-
#define KEYNUM_31 10 //关键字个数,这里为整形位数
-
void RadixSort(int* pDataArray, int iDataNum)
-
{
-
int *radixArrays[RADIX_10];
-
for (int i = 0; i < 10; i++)
-
{
-
radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
-
radixArrays[i][0] = 0;
-
}
-
-
for (int pos = 1; pos <= KEYNUM_31; pos++)
-
{
-
for (int i = 0; i < iDataNum; i++)
-
{
-
int num = GetNumInPos(pDataArray[i], pos);
-
int index = ++radixArrays[num][0];
-
radixArrays[num][index] = pDataArray[i];
-
}
-
-
for (int i = 0, j =0; i < RADIX_10; i++)
-
{
-
for (int k = 1; k <= radixArrays[i][0]; k++)
-
pDataArray[j++] = radixArrays[i][k];
-
radixArrays[i][0] = 0;
-
}
-
}
-
}
阅读(1163) | 评论(0) | 转发(0) |