C/C++知识点之基数排序及C语言实现-职坐标

C/C++知识点之基数排序及C语言实现

小标 2018-11-13 来源：阅读 938 评论 0

摘要：本文主要向大家介绍了C/C++知识点之基数排序及C语言实现，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了C/C++知识点之基数排序及C语言实现，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

基数排序的基本思想是对数字的每一位进行排序，先对个位排序，然后十位，百位……，对每一位进行排序时，要求采用稳定排序算法，比如前面讨论过的计数排序。以一个三位整数为例，过程是这样的：

该算法同样能达到线性复杂度。下面是代码。（好吧，我知道写的很菜……）
#include
#define NUM 10  //数组元素个数

void counting_sort(int a[],int b[],int c[],int atemp[]);
int main()
{
int i;
int j;

int a[10] = {326,54,512,13,9,71,92,61,53,19}; //input array
int atemp[10];
int b[10]; //output array
int c[10]; //temp all element are not biger than 10

// 个位排序
for (i = 0;i < NUM;i++)
  atemp[i] = a[i] % 10;
counting_sort(atemp,b,c,a);
for (i = 0;i < NUM;i++)
  a[i] = b[i];

// 十位排序
for (i = 0;i < NUM;i++)
  atemp[i] = a[i] / 10 % 10;
counting_sort(atemp,b,c,a);
for (i = 0;i < NUM;i++)
  a[i] = b[i];
//百位排序
for (i = 0;i < NUM;i++)
  atemp[i] = a[i] / 100 % 10;
counting_sort(atemp,b,c,a);

for (i = 0;i < NUM;i++)
  printf(" %d ",b[i]);
printf("\n");

}
//计数排序算法，a为待排序数组(一位数，要和atemp区分开)，b为排序好的数组,c为中间数组，atemp为原始数组(包括三位数)
void counting_sort(int a[],int b[],int c[],int atemp[])
{
int i,j;
for (i = 0;i < NUM;i++)
  c[i] = 0;
for (j = 0;j < NUM;j++)
  c[a[j]] += 1;
for (i = 1;i < NUM;i++)
  c[i] = c[i] + c[i-1];
for (j = 9;j >= 0;j--) {
  b[c[a[j]] - 1] = atemp[j];
  c[a[j]] -= 1;
}
}