#include
#include
#include#define Length 10
using namespace std;
void CountSort(int numa[], int len, int range, int d);
//参数: 带排序数组数组长度数组中元素从0到最大值的取值个数数组的位数
void RadixSort(int num[], int len, int d);
//待排数组 数组长度 最大元素的位数
void Output(int num[], int len);
int main()
{
int numa[Length] = {12, 112, 34, 56, 26, 8, 31, 6, 20, 3};
RadixSort(numa, Length, 3);
Output(numa, Length);
}void RadixSort(int numa[], int len, int d)
{
for(int i = 0;
i < d;
i++)
{
CountSort(numa, len, 9, i);
//运用for循环 将数组元素从低位到高位依次进行计数排序
Output(numa, Length);
}
} void CountSort(int numa[], int len, int range, int d)//基数排序利用的是计数排序是一个稳定的排序算法
{
int numc[range], numb[len];
int j = (int)pow(10, d);
//j：1， 10...
for(int i = 0;
i < range;
i++)
{
numc[i] = 0;
}
for(int i = 0;
i < len;
i++)
{
numc[numa[i] / j % 10]++;
//此时得到的是原数组元素第 j+1 位的值
}
for(int i = 1;
i < range;
i++)
{
numc[i] += numc[i - 1];
}
for(int i = len - 1;
i >= 0;
i--)
{
numb[numc[numa[i] / j % 10] - 1] = numa[i];
numc[numa[i] / j % 10]--;
}
for(int i = 0;
i < len;
i++)
numa[i] = numb[i];
//必须将排序号的数组拷贝回原数组numa！！！！ 因为是numa不断参与循环
}void Output(int num[], int len)
{
for(int i = 0;
i < len;
i++)
{
printf("%d", num[i]);
}
cout << endl;
}
【[算法导论]基数排序】
推荐阅读
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 【算法导论之四】计数排序
- 算法导论计数排序实现