/*********************************************************************** 基数排序---用数组模拟桶 思路:待排序数组 。一个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); }
原文:http://blog.csdn.net/lynnbest/article/details/21563839