基数排序及流程图

包括了基数排序的实现代码和流程图。 先对个位数字进行统计，然后根据个位进行排序，然后对十位进行统计，然后根据十位进行排序，即可获得最终结果。 时间效率：待排序列为n个记录，10个关键码，关键码的取值范围为0-9，则进行链式基数排序的时间复杂度为O(4(n+10))，其中，一趟分配时间复杂度为O(2（n+10)，一趟收集时间复杂度为O(2（n+10)，共进行2趟分配和收集。

//基数排序的实现文件
#include “f_radix_sort.h“
void f_radix_sort（int *aint n）
{
	int ij;//定义2个循环变量
	int barrel[10]={0};//定义一个桶数组，记录每位数字有多少
	int seat[10]={0};//定义一个位置数组，记录该次某一个数字排序的位置
	int* b=（int*）malloc（sizeof（int）*n）;//申请一块内存，用来存储排序之后的a
	for（i=0;i	{
		b[i]=0;
	}
	for（i=0;i	{
		for（j=0;j<10;j++）//桶中坐标
		{
			if（*（a+i）%10==j）//对个位进行记录，并放入barrel相应的位置中
			{
				barrel[*（a+i）%10]++;
			}
		}
	}
	for（i=1;i<10;i++）//记录某位在排序中的位置
	{
		seat[i]=seat[i-1]+barrel[i-1];
	}
	for（i=0;i	{
		b[seat[（a[i]%10）]++]=a[i];
	}
	for（i=0;i	{
		a[i]=b[i];
	}
	for（i=0;i<10;i++）//对桶和位置进行初始化，进行下一次使用
	{
		barrel[i]=0;
		seat[i]=0;
	}
	//以下为十位的排序，结果和个位类似
	for（i=0;i	{
		for（j=0;j<10;j++）
		{
			if（*（a+i）/10%10==j）
			{
				barrel[*（a+i）/10%10]++;
			}
		}
	}
	for（i=1;i<10;i++）
	{
		seat[i]=seat[i-1]+barrel[i-1];
	}
	for（i=0;i	{
		b[seat[（a[i]/10%10）]++]=a[i];
	}
	for（i=0;i	{
		a[i]=b[i];
	}
	free（b）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        213  2013-02-22 14:10  test.c

     文件      61440  2013-02-22 14:41  基数排序.doc

     文件       1223  2013-02-22 14:22  f_radix_sort.c

     文件        108  2013-02-22 09:57  f_radix_sort.h

----------- ---------  ---------- -----  ----

                62984                    4