（9）排序算法——分配式排序之基数排序

发表于   |   分类于   |   阅读次数

1、概述：

基数排序与桶排序类似，只是利用桶的方式不同。这里总是使用10个桶（0~9）。简单来说是按位比较，先按个位比较排序，再按十位比较，以此类推，知道所有的位都比较完成。

基数排序有两种：

  • 一种是最低位优先(Least Significant Digit first)法，简称LSD法：先从最低位开始排序，然后排高一位，直到最高位。一般采用这种方式。
  • 一种是最高位优先(Most Significant Digit first)法，简称MSD法：先按最高位排序，在同一组中，按照较低一位排序，直到按个位排序。排完之后将各组数据串联起来就是一个有序序列了。这里就类似于桶排序了。

2、算法描述：

假设有数组{99,120, 32,77,54,8,32,129,21,17}，利用基数排序进行升序排列。以LSD为例。

  1. 首先根据数组元素的个位，将他们按照从小到大排列在0~9个桶内。
  2. 然后将所有数据重新串联起来，生成一个新的数组。
  3. 接着再根据十位进行排列，完成后重新生成数组。
  4. 再根据百位进行排列，生成新的数组。完成后数组就排好序了。

图解说明如下：


3、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 基数排序
 * @author lizhen
 */
public class RadixSort {
	/**
	 * 升序排列
	 * @param arr 
	 */
	public void radixSort(int[] arr,int maxl){
		//生成一个长度为10的桶，每个桶由一个线性表构成。
		ArrayList<Integer>[] list = new ArrayList[10];
		//设置取=按照哪一位的数据来排序。
		int m = 1;
		int n = 1;
		while(m<=maxl){
			//循环取arr中元素，并根据个位找到元素应该放到哪个桶中。
			for(int i=0;i<arr.length;i++){
				int index = (arr[i]/n)%10;
				if(null==list[index]){
					list[index] = new ArrayList<Integer>();
				}
				list[index].add(arr[i]);
			}
			//list数据合并到arr中
			int count = 0;//数组游标
			for(int k=0;k<list.length;k++){
				if(null!=list[k]){
					//遍历每一个桶里的list，顺序合并至数组
					Iterator iterator = list[k].iterator();
					while(iterator.hasNext()){
						arr[count] = (Integer) iterator.next();
						count++;
					}
				}
			}
			//清空数组
			Arrays.fill(list, null);
			n = n*10;
			m++;
		}
	}
}