基数排序(radix sort）是属于“分配式排序”（distribution sort），基数排序又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
实现方法：最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
Java代码示例：
package com.sort.pattern;
import java.util.ArrayList;
import java.util.Arrays;
/**
* LSD基数排序
*
* @author louxuezheng 2014年4月2日
*/
public class RadixSortDemo {
public void radixSort(int[] a) {
// 1 找最大数
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
// 2 计算最大数的位数
int time = 0;
while (max > 0) {
max /= 10;
time++;
}
// 3 创建10个用于排序的桶， 每个桶中用于存放制定位数相等的数
ArrayList<ArrayList<Integer>> queue = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> subqueue = new ArrayList<Integer>();
queue.add(subqueue);
}
// 4 把数组中的数进行分配和收集
for (int i = 0; i < time; i++) {
// 根据计算的位数值放入相应的桶中
for (int j = 0; j < a.length; j++) {
int x = a[j] % (int) Math.pow(10, i + 1)
/ (int) Math.pow(10, i);
queue.get(x).add(a[j]);
}
// 对桶中数据收集排序
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
a[count] = queue.get(k).get(0);
queue.get(k).remove(0);
count++;
}
}
}
}
public static void main(String[] args) {
RadixSortDemo rsd = new RadixSortDemo();
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
99, 98, 54, 101, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51, 1021,
2105, 2222 };
rsd.radixSort(a);
System.out.println(Arrays.toString(a));
}
}
Java编程思想(第4版) 中文清晰PDF完整版