—基数排序—
基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;
算法描述
具体算法描述如下:
<1>.取得数组中的最大数,并取得位数;
<2>.arr为原始数组,从最低位开始取每个位组成radix数组;
<3>.对radix进行计数排序(利用计数排序适用于小范围数的特点);
代码实现
int Max_Radix(int a[], int n) //辅助函数,求数据的最大位数
{
int max = a[0]; /// 最大数
for (int i = 1; i < n; ++i) /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数
{
if (a[i] > max)
max = a[i];
}
int count = 1; //用于判断之后循环几次
while ((max/=10) != 0)
count++;
return count;
}
void Radix_Sort(int a[],int n) //基数排序 类似于计数排序
{
int count = Max_Radix(a, n); //count =2
int* temp = new int[n]; //存放临时数组
int* index = new int[10]; // 计数器 0~9
int p = 1; //先从个位开始
for (int i = 1; i <= count;++i) //进行count次排序
{
for (int i = 0; i < 10; ++i)
index[i] = 0;
for (int i = 0; i < n; ++i)
index[(a[i] / p) % 10]++;
for (int i = 1; i < 10; ++i)
index[i] += index[i - 1];
for (int i = 0; i < 10; ++i)
cout << index[i] << " ";
cout << endl;
for (int i =n-1; i >=0 ; --i) // 一定从后往前遍历,这样不会乱序 从前往后会乱序。
{
temp[index[(a[i] / p) % 10] - 1] = a[i]; //注意不能写成 index[((a[i] / p) % 10)] - 1] 形式
index[(a[i] / p) % 10]--;
}
for (int i = 0; i <n; i++)
a[i] = temp[i];
p *= 10;
}
}
算法分析
平均情况:T(n) = O(n * k)
最佳情况:T(n) = O(n * k)
最差情况:T(n) = O(n * k)
稳定性
- 稳定
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com