/*测试数据要求：不能是负数，同一数位上相同的数有一定限制*/
#include
#include
#include
#include
using namespace std;
const int bitmaxsize = 50;
//在同一位上相同的数的个数，一般情况下有数据个数的一半基本能满足要求
const int Maxarrsize = 100;
//数组数据个数
void radixsort(int * arr, int num1, int num2, int n);
int getnumbit(int * arr, int length);
void print(int * arr, int length);
int main()
{
srand(time(0));
int m[Maxarrsize] = { 0 };
for (int i = 0;
i < Maxarrsize;
++i)
m[i] = rand();
//m[68] = 26905;
为什么此处加入六位数的时候会出现程序崩溃
const int arrsize = sizeof(m) / sizeof(int);
print(m, arrsize);
//cout << INT_MAX << "*****************\n";
//cout << pow(2, 31) << "*****************\n";
radixsort(m, 0, arrsize-1, getnumbit(m, arrsize));
print(m, arrsize);
return 0;
}
int getnumbit(int * arr, int length)
{
if (length <= 0)return 0;
else
{
int i = 10;
for (;
i>0;
--i)
{
for (int j = 0;
j < length&&j >= 0;
++j)
{
int t = pow(10, i);
if (arr[j] / t != 0)return i + 1;
}
}
return 0;
}
}
void print(int * arr, int length)
{
for (int i = 0;
i < length;
++i)
cout << arr[i] << "\t";
cout << endl;
}
void radixsort(int * arr, int num1, int num2, int n)
{
struct heap
{
int m[bitmaxsize];
int count = 0;
};
heap *g=new heap[10];
for (int i = 1;
i <= n;
++i)
{
int f = pow(10, i-1);
for (int j = 0;
j < num2 - num1+ 1;
++j)
{
int t = (arr[j] / f) % 10;
g[t].m[g[t].count++] = arr[j];
}
int h = num2;
for (int j = 9;
j >-1 ;
--j)
{
for (;
g[j].count > 0&&h>-1;
h--)
{
arr[h] = g[j].m[--g[j].count];
}
}
}
cout << endl;
//for (int i = 0;
i < 10;
++i)
// delete []g[i].m;
delete[]g;
}
推荐阅读
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 算法|算法-二分查找
- 刷题记录|【蓝桥必胜】试题 算法训练 kAc给糖果你吃-贪心排序
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 算法|用Python 实现的九种排序算法
- 数据结构|Java排序算法详解_七大基于比较的排序算法
- 算法|数据结构（基数排序）
- 算法|java排序 冒泡排序，选择排序，插入排序，希尔排序，快速排序
- 数据结构|数据结构学习之基数排序（含C++代码）