基数排序原理及JAVA实现

分配类排序

• 分配类排序：又称桶子法（bucket sort），是唯一一种不需要进行关键字之间比较的排序方法。
• 基本思想：利用分配和收集两种基本操作来达到排序的目的。

基数排序属于分配类排序。

基数排序定义

对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，可以采用“分配-收集”的办法进行排序，称为基数排序法。

实现原理

将待排序列（正整数）统一为同样的数位长度，数位较短的数前面补0,。然后，从最低位开始，依次进行一次排序。这样从最低位一直到最高位排序完成以后，数列就变成一个有序序列。

实现方法

假设有n个记录的序列{K0， K1， ……， K(n-1)}，每个记录Ki中含有d个关键字（Ki0， Ki1，……， Ki(d-1)），则上述记录序列对关键字（Ki0， Ki1，……， Ki(d-1)）有序是指：对于序列中任意两个记录Ki和Kj（0 <= i <= j <= n-1）都满足下列有序关系：（Ki0， Ki1，……， Ki(d-1)）  < （Ki0， Ki1，……， Ki(d-1)），其中K0称为“最主”位关键字，K(d-1)称为“最次”位关键字。

• MSD法，即最高位优先（Most Significant Digit first）法：先按K0排序分组，同一组中记录，关键码K0相等，再对各组按K1排序分组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码K(d-1)对各子组排序后。再将各组连接起来，便得到一个有序序列。
• LSD法，即最低位优先（Least Significant Digit first）法：先从K(d-1)开始排序，再对K(d-2)进行排序，依次重复，直到对K0排序后便得到一个有序序列。

基本步骤

1. 分配：按当前“关键字位”所取值，将记录分配到编号为0~9的桶子中；
2. 收集：按当前关键字位取值，将这些桶子中的记录重新串连起来，形成新的序列；
3. 重复：对每个关键字位均重复1、2两步。

具体实现

待排序列为{12， 8645， 328， 8， 1234， 98， 36， 5}，给出基数排序的具体过程。（LSD法）

步骤一：分配。把待排序列记录按个位数值分配到编号为0~9的桶子中。

步骤二：收集。把桶子中的记录重新连接起来，形成新的序列。

步骤三：重复步骤一、二。

（1）把待排序列记录按十位数值分配到编号为0~9的桶子中。

（2）把桶子中的记录重新连接起来，形成新的序列。

（3）把待排序列记录按百位数值分配到编号为0~9的桶子中。

（4）把桶子中的记录重新连接起来，形成新的序列。

（5）把待排序列记录按万位数值分配到编号为0~9的桶子中。

（6）把桶子中的记录重新连接起来，形成新的序列。

此时，发现待排序列已经变为有序序列。则，排序完毕。

代码实现

import java.util.Arrays;

public class RadixSort {
	
	public static void radixSort(int[] arr, int digit, int maxLen) {
		int[] count = new int[digit];
		int[] temp = new int[arr.length];
		int divide = 1;
		
		for(int i = 0; i < maxLen; i++) {
			//每次分配之前，先把arr数值的记录拷贝一份给temp数组
			System.arraycopy(arr, 0, temp, 0, arr.length);
			//然后对桶子进行清空
			Arrays.fill(count, 0);
			
			//把记录分配到桶子中
			for(int j = 0; j < arr.length; j++) {
				//取出下标为j的记录的第i个关键字的值
    			int tempKey = (temp[j]/divide)%digit;
    			count[tempKey]++;
    		}
    		
    		for(int j = 1; j < digit; j++) {
    			count[j] += count[j-1];
    		}
    		
    		for(int j = arr.length-1; j >= 0; j--) {
    			int tempKey = (temp[j]/divide)%digit;
    			count[tempKey]--;
    			arr[count[tempKey]] = temp[j];
    		}
    		
    		divide = digit * divide;
    	}
	}
	
	private static void showArr(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {12, 8645, 328, 8, 1234, 98, 36, 5};
		/*
		 * 基数排序
		 * 10表示数字的进制
		 * 4为待排序列中记录的最大位数
		 */
		radixSort(arr, 10, 4);
		showArr(arr);
	}
}

运行结果

效率

时间复杂度：O（d(n+r)）；

空间复杂度：O（n+r）；

稳定性：稳定排序。

说明：其中，d 为位数，r 为基数，n 为原数组个数。

参考资料：《数据结构与算法》    王曙燕    主编    王春梅    副主编    人民邮电出版社