基数排序（LSD+MSD）详解

大家好，又见面了，我是你们的朋友全栈君。

基数排序

分为两类：

第一类：最低位优先法，简称LSD法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；具体过程如下图所示：

初始数组序列为：15,25,105,78,34,21,32,41，按照个位数大小依次入桶；

将桶中数依次倒出，对于同一个桶中的数按先进先出顺序倒出，结果为：21,41,32,34,15,25,105,78，再按十位数大小依次入桶；

将桶中数依次倒出，结果为：105,15,21,25,32,34,41,78，再按百位上数大小依次入桶，没有百位的数则按百位为0入桶；

将桶中数倒出，结果为：15,21,25,32,34,41,78,105

Java实现代码如下：

public void radixSort(int[] A,int n){
		int max = A[0];
		for(int i = 1 ;i < n;i++){
			if(max < A[i])
				max = A[i];
		}
		double d = Math.pow(10, String.valueOf(max).length());
		
		int k = 1;
		int[][] t = new int[10][n];  //桶
		int[] num = new int[n];  //记录每个桶中存入数的个数
		while(k < d){
			for(int a : A){
				int m = (a / k) % 10;
				t[m][num[m]] = a;
				num[m]++;
			}
			int c = 0;
			for(int i = 0; i < n; i++){
				if(num[i] != 0){
					for(int j = 0;j < num[i];j++){
						A[c++] = t[i][j];
					}
				}
				num[i] = 0;
			}
			k = k * 10;
		}
		
	}

第二类：最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。

仍以序列：15,25,105,78,34,21,32,41为例，从最高位百位依次入桶，只有105有百位，其他百位按0算；检测每个桶中的数据。当桶中的元素个数多于1个的时候，要对这个桶递归进行下一位的分组。

Java代码实现：

public class MSDSort {
	public int[] sort(int[] A, int n){
		int max = A[0];
		for(int i = 1 ;i < n;i++){
			if(max < A[i])
				max = A[i];
		}
		int maxL = String.valueOf(max).length();  //获取数组中最长元素长度
		
		int k = new Double(Math.pow(10, maxL - 1)).intValue();
		int[][] t = new int[10][n];  //桶
		int[] num = new int[n];      //记录每个桶中存入数的个数
		
		for(int a : A){              //按最高位入桶
			int m = (a / k) % 10;
			t[m][num[m]] = a;
			num[m]++;
		}
		int c = 0;
		for(int i = 0; i < n; i++){
			if(num[i] == 1){        //如果桶中只有一个数则直接取出
				A[c++] = t[i][0];
			}else if(num[i] > 1){   //如果桶中不止一个数，则另存如数组B递归
				int[] B = new int[num[i]]; 
				for(int j = 0;j < num[i];j++){
					B[j] = t[i][j];
					sort(B,num[i]);   //递归方法
				}
			}
		}
		return A;
	}
	public static void main(String[] args) {
		RadixSort r = new RadixSort();
		int[] A = {12,1,23,123,34};
		r.sort(A, A.length);
		for(int a : A){
			System.out.println(a);
		}

	}

}