Java排序算法总结（八）：基数排序

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

效率分析：

时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(n)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

实现方法：

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

代码实现：

public class RadixSort {   



public static void sort(int[] number, int d) {   




int k=0;   




int n=1;   




int m=1;   




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]++;   


}   



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的辅助空间，快速排序需要一个栈。除了快速排序、堆排序、选择排序、希尔排序不稳定外，其它排序方法都是稳定的。