基数排序+桶排序
程序员文章站
2022-03-24 15:32:36
...
基数排序
缺点:空间复杂度大;不能有重复的数字
对于b[a[i]] = a[i];
的理解
比如在循环赋值的过程中,对于大小为3的数组a[3],有a[0] = 2,a[1]=5,a[2]=9;
那么有b[2]=2, b[5]=5, b[9] = 9
,其余的b[0],b[1],b[3],b[4],b[6],b[7],b[8]均为初值-1
,见代码。
#include<vector>
#include <tchar.h>
#include<iostream>
void radix_sort(int* a, int len, int max)
{
//1.创建临时数组
int* b = new int[max + 1]; //因为要当下标用,所以下标为max的数组长度为max+1
//2.初始化临时数组
for (int i = 0; i <= max; i++)
{
b[i] = -1;
}
//3.排序
for (int i = 0; i < len; i++)
{
b[a[i]] = a[i]; //i=10
}
//4.把b数组元素赋值回a数组(因为b数组中有很多为-1的值)
int j = 0;
for (int i = 0; i <= max; i++)
{
if (b[i] != -1)
{
a[j++] = b[i]; //将a[j] = b[i]后,j自加;
}
}
//5.释放临时数组
delete[] b;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[10] = { 9, 5, 7, 3, 4, 1, 0, 6, 8, 2 };
int length = sizeof(a) / sizeof(int);
radix_sort(a, length,9);
for (int i = 0; i < length; i++)
{
printf("%3d",a[i]);
}
system("pause");
}
未完待续。。。。。