基数排序--数组模拟桶结构

/***********************************************************************
基数排序---用数组模拟桶
思路：待排序数组 。一个index[10]数组。一个临时数组。
按照位数从低位开始排序。即是从个位开始。归类。然后收集。在从十位开始，归类。然后在收集。
分配--收集  这两个过程
**********************************************************************/
#include <stdio.h>
#include <string.h>
void PrintArray(int a[],int len)
{
	for(int i=0;i<len;i++)
		printf("%d ",a[i]);
	printf("\n");
}
// 获取 int x的第bitnum位. 比如取23的第一位 返回3
int getdigit(int x,int bitnum)
{
	int tmp[]={0,1,10,100}; // tmp[0]忽略。tmp[1]取个位，tmp[2]取十位,tmp[3]取百位
	return (x/tmp[bitnum])%10;
}
/**********************************************************************
基数排序
************************************************************************/
void LsdRadixSort(int a[],int len,int maxbitnum)
{
	int index[10];	//  索引数组 0~9 索引值 比如 23 那么个位的话，应该就是在index[3]内
	int  *Bucket=new int[len]; //用于临时存储收集使用
	if(NULL==Bucket)
		return ;
	int i,j;
	for(int k=1;k<=maxbitnum;k++) // 从个位开始-第一位
	{	
		memset(index,0,sizeof(index)); //初始化
		for(i=0;i<len;i++) // 统计某位上出现数总和。比如 index[0]=3表明个位为3的有3个数
			++index[getdigit(a[i],k)];
		
		for(i=1;i<10;i++)//统计至此索引为止共出现的个数比如 index[4]=5表明至此为止共有5个数了
			index[i]=index[i]+index[i-1]; //也就是index[4] 应该成为桶数组的第5个数(对应bucket[4])
		
		for(i=len-1;i>=0;--i) // 按照某位进行分配 注 从右往左这样保持稳定性
		{	
			j=getdigit(a[i],k);
			Bucket[index[j]-1]=a[i];
			--index[j];	//注意要字自减
		}
		// 收集 bucket[i]至 a[]中
		for(i=0;i<len;i++)
			a[i]=Bucket[i];
	}
	delete [] Bucket;
	Bucket=NULL;
}
int main()
{
	int a[]={24,12,22,45,89,100,10}; 
	puts("--------排序前----------");
	int len=sizeof(a)/sizeof(int);
	PrintArray(a,len);
	LsdRadixSort(a,len,3);
	puts("--------排序后----------");
	PrintArray(a,len);
}

基数排序--数组模拟桶结构,布布扣,bubuko.com

基数排序--数组模拟桶结构

原文：http://blog.csdn.net/lynnbest/article/details/21563839