定义
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
原理图
我们现在有一个无序数组:[ 86,77,49,36,48,55,40,65,57,37]
排个位数:
此时数组序列变为:[40,55,65,86,36,77,57,37,48,49]
排十位:
此时变为有序数组:[36,37,40,48,,49,55,57,65,77,86]
代码实现
size_t GetMaxDigit(size_t *arr, size_t len)
{
size_t digit = 1;
size_t base = 10;
for (size_t i = 0; i < len; i++)
{
while (arr[i] >= base)
{
base *= 10;
digit++;
}
}
return digit;
}
void LSDSort(size_t *arr, size_t len)
{
size_t maxDigit = GetMaxDigit(arr, len);
size_t base = 1;
size_t *bucket = new size_t[len];
while ((maxDigit--) > 0)
{
size_t counts[10] = { 0 };
size_t start[10] = { 0 };
start[0] = 0;
for (size_t i = 0; i < len; i++)
{
size_t num = (arr[i] / base) % 10;
counts[num]++;
}
for (size_t i = 1; i < 10; i++)
{
start[i] = start[i - 1] + counts[i - 1];
}
for (size_t i = 0; i < len; i++)
{
size_t num = (arr[i] / base) % 10;
bucket[start[num]++] = arr[i];
}
memcpy(arr, bucket, sizeof(size_t)*len);
base *= 10;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)