基数排序--MSD（桶排序）

【基数排序】(radixsort）则是属于“分配式排序”（distributionsort），基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法，同时基数排序分最高位优先"(MSD)法和最低位优先"(LSD)法。

下面我们要讲的是MSD；（MSD比LSD更加实用）

简略概述：基数排序是通过“分配”和“收集”过程来实现排序。而这个思想该如何理解呢？请看以下例子。

（1）将数组：12  14  54  5  6  3  9  8  47  89排序

首先根据最高位十位在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

0    5 6 3 9 8

1    12 14  

2         

3        

4    47    

5    54    

6        

7        

8    89    

9        

 

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

5 6 3 9 8 12 14 47 54 89

然后再将每个桶分0-9号小桶，因为1-9号桶最多只有1个数，所以不再列出

0号桶分配结果（逻辑想象）如下图所示：

 

0        

1        

2         

3     3    

4         

5     5    

6     6    

7        

8     8    

9     9    

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

3 5 6 8 9 12 14 47 54 89

（2）我们把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。

要求如下：

花色顺序：梅花<方块<红心<黑桃

面值顺序：2<3<4<...<10<J<Q<K<A

那么，若要将一副扑克牌排成下列次序：

梅花2，...，梅花A，方块2，...，方块A，红心2，...，红心A，黑桃2，...，黑桃A。

<1>先按花色分成四堆，把各堆收集起来；然后对每堆按面值由小到大排列，再按花色从小到大按堆收叠起来。----称为"最高位优先"(MSD)法。

 

（1）MSD法实现

最高位优先法通常是一个递归的过程：

<1>先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。

<2>再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。

<3>依此重复，直到对关键码Kd完成排序为止。

<4> 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。

 

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<malloc.h>
using namespace std;
const int maxn=1e6+7;
int arr[maxn]={12,14,54,5,6,3,9,8,47,89};
int getdigit(int x,int d){
	int a[]={1,1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9};	////因为待排数据最大数据位数
	return ((x/a[d])%10);
}
void msdradix_sort(int begin,int end,int d){
	const int radix=10;	//进制数
	int count[radix],i,j;	//count表示每个桶中元素个数	
	//置零
	for(i=0;i<10;++i)count[i]=0;
	//给桶分配空间
	int *bucket=(int *)malloc((end-begin+1)*sizeof(int));
	//统计各桶需要装的元素的个数
	for(i=begin;i<=end;++i){
		count[getdigit(arr[i], d)]++;
	}
	//求出桶的边界索引，count[i]值为第i个桶的右边界索引+1
	for(i=1;i<radix;++i){
		count[i]+=count[i-1];	//每个桶的边界，便于下步将arr重新放入bucket里 
	}
	//这里要从右向左扫描，保证排序稳定性 
	for(i=end;i>=begin;--i){
		j=getdigit(arr[i],d);		  //求出关键码的第d位的数字， 例如：576的第3位是5 
		bucket[count[j]-1]=arr[i];	  //放入对应的桶中，count[j]-1是第j个桶的右边界索引
		--count[j]; 			 //第j个桶放下一个元素的位置(右边界索引+1)  
	}
	//注意：此时count[i]为第i个桶左边界    
    //从各个桶中收集数据  
	for(i = begin, j = 0;i <= end; ++i, ++j){
        arr[i] = bucket[j]; 
    } 
	//释放存储空间
	free(bucket);	
	//对每个桶再次排序
	for(i=0;i<radix;i++){
		int p1=begin+count[i];	//第I个桶的左边界
		int p2=begin+count[i+1]-1 ;	//第i个桶的右边界
		if(p1<p2&&d>1){
			msdradix_sort(p1, p2, d-1);  //对第i个桶递归调用，进行基数排序，数位降 1  
		} 
	}
}
int main(){
	int len=10;
	for(int i=0;i<10;i++)cout<<arr[i]<<" ";
	cout<<endl;
 	msdradix_sort(0,10-1,2); //2表示最高位数 
	for(int i=0;i<10;i++)cout<<arr[i]<<" ";
	cout<<endl;	
}