基数排序

基数排序算法

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

基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献[1]。

它是这样实现的： 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用LSD（Least significantdigital）或MSD（Most significantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

以LSD为例，假设原来有一串数值如下所示：

73,22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

　　0

　　1 81

　　2 22

　　3 73 93 43

　　4 14

　　5 55 65

　　6

　　7

　　8 28

　　9 39

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81,22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

　　0

　　1 14

　　2 22 28

　　3 39

　　4 43

　　5 55

　　6 65

　　7 73

　　8 81

　　9 93

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14,22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都是相同。

package com.radixSort.yy;
/**
 * 基数排序
 *@author yuyang_csu
 *@data 2013-4-8
 */
public class RadixSort {
	/**
	 * 
	 * @param number
	 *            :待排序的序列
	 * @param d
	 *            ：序列中最大数的位数
	 */
	public static void sort(int[] number, int d) {
		int k = 0;
		int n = 1;
		// 控制键值排序依据在哪一位
		int m = 1;
		// 声明一个代表桶的二维数组，列数代表桶的编号0~9,行号代表该桶中有几个元素，值代表元素的值
		int[][] temp = new int[number.length][number.length];
		// 计数数组，记录每个桶中有几个元素
		int[] order = new int[number.length];

		while (m <= d) {
			//按照位数比较，将元素一次放在当前比较位上数字所对应的桶中
			for (int i = 0; i < number.length; i++) {
				//控制输出比较位上的数字
				int lsd = ((number[i] / n) % 10);
				temp[lsd][order[lsd]] = number[i];
				order[lsd]++;
			}
			//将桶中的元素分别取出，再重新copy到原数组中
			for (int i = 0; i < d; i++) {
				if (order[i] != 0)
					for (int j = 0; j < order[i]; j++) {
						number[k] = temp[i][j];
						k++;
					}
				order[i] = 0;
			}
			n *= 10;
			k = 0;
			m++;
		}
	}

	// 主函数
	public static void main(String[] args) {
		int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100 };
		RadixSort.sort(data, 10);
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
}

时间效率分析：给定n个d位数，每一个数位可以取k种可能值。基数排序的时间效率为O（d(n+k)）。

稳定性分析：稳定的。