基数排序与基数排序是两种非比较型排序。
计数排序：
//************计数排序*********
//先大-最小+1得到开辟空间数，开辟空间str，在遍历原数据arr在str相应位置计数，再遍历str将值写到原arr中
//适用在密集型数据， 无重复最优可转化为位图
//时间复杂度O(N),空间复杂度O(大数-最小数+1)
//设数组元素非负
void CountingSort(int *a, size_t size)
{
size_t i = 0, j = 0;
int max = a[0], min = a[0];
size_t space = 0;
for (i = 1; i < size; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
space = max - min + 1;
//str相应位置记录a中个数据的次数
int *str = new int[space]();
for (i = 0; i < size; i++)
{
str[a[i] - min] ++;
}
//写回原数组a中
for (i = 0, j = 0; i < space, j < size; i++)
{
while (str[i]-- > 0)
{
a[j++] = i + min;
}
}
}基数排序：
//***********基数排序**************
//采用先排低位，在排高位
//时间复杂度O(位数) 空间复杂度O(N)
//设数组元素非负
size_t GetMaxRadix(int *a, size_t size)//取数组中大值的位数
{
assert(a != NULL);
size_t i = 0;
size_t num = 0;
size_t count = 1;
for (i = 0; i < size; i++)
{
while (a[i] / count>0)
{
count *= 10;
num++;
}
}
return num;
}
void LSDSort(int *a, size_t size)
{
assert(a != NULL);
int MaxRadix = GetMaxRadix(a, size);
int count[10] = { 0 };//同一位上数字相等的数字个数
int start[10] = { 0 };//按位上数字所对应的起始位置
int * bucket = new int[size];
size_t i = 0;
int num = 1;
while (MaxRadix--)
{
memset(count, 0, sizeof(int) * 10);//count清零
//按位排序
for (i = 0; i < size;i++)//count[]
{
count[a[i] / num % 10]++;//取某一位上数字，在count相应位置++
}
for (i = 0; i < 10; i++)//start[]
{
//跳过0 因为起始位置一定为0
if (i == 0)
{
start[i] = 0;
}
else
start[i] = start[i - 1] + count[i - 1];
}
//写到bucket[]中
for (i = 0; i < size; i++)
{
bucket[start[a[i] / num % 10]++] = a[i];
}
//写回a[]中
for (i = 0; i < size; i++)
{
a[i] = bucket[i];
}
num *= 10;
}
}test:
int a5[] = { 5, 24, 35, 54, 72, 81, 75, 6, 9, 56, 114, 30, 5 };
int a6[] = { 5, 24, 35, 54, 72, 81, 75, 6, 9, 56, 114, 30, 5 };
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。