基数排序及C语言实现

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


该算法同样能达到线性复杂度。下面是代码。(好吧,我知道写的很菜……)

#include <stdio.h>
#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;
	}
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。