排序 - 基数排序（5）

水深无声 2022-10-02 13:59 80阅读 0赞

**概念**

基数排序是根据组成关键字的各位值，用“分配”和“收集”的方法进行排序。

**实现方法**

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

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

**排序演示**

1.  第一步：获得记录中最大的数的位数
2.  第二步：根据个位将记录按照0-9分桶（分配）
3.  第三步：将0-9的桶的记录的按顺序覆盖原待排序的记录（收集）
4.  第四步：将第三步重新排序的记录根据十位将记录按照0-9分桶（分配）
5.  第五步：将0-9的桶的记录的按顺序覆盖原待排序的记录（收集）
6.  ......
7.  直到最大位数分桶，数据就是最终记录。

![70][]

**实现代码**

public static void sort(int[] number) { 
                    //第一步：求出待排序数组中的元素的最大长度
                    int d=Integer.MIN_VALUE;
    		for(int i=0;i<n;i++){
    			d=d>(Integer.toString(data[i]).length())?d:(Integer.toString(data[i]).length());		
    		}
    		int k=0;
    		int n=1;
    		int m=1;//控制键值排序依据在哪一位
    		int[][] temp=new int[10][number.length];//数组的第一维度表示可能的余数0-9
    		int[] order=new int[10];//数组order[i]表示该位是i的数的个数
    		while(m<=d) {
    			//分配
    			for(int i=0;i<number.length-1;i++) {
    				int last=((number[i]/n)%10);
    				temp[last][order[last]]=number[i];
    				order[last]++;
    			}
    			//收集：按照桶来收集
    			for(int i = 0; i < 10; 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++;
    		}
    		
    	}

**算法分析**

1.  时间复杂度  
    第一步求元素最长长度的时间复杂度为O（n）  
    分配的时间复杂度为O（n）
    
    收集的的时间复杂度为O（m）,m为堆数  
    分配和收集共需要distance趟  
    所以基数排序的时间复杂度为O(d(n+m)+n)  
    我们可以看出，基数排序的效率和初始序列是否有序没有关联
2.  空间复杂度  
    O（n）
3.  算法稳定性  
    基数排序法是属于稳定性的排序，在某些时候，基数排序法的效率高于其它的稳定性排序法。

**使用场景**

假设主关键字可以分拆成d位，每一位取值范围为j个值，整个排序需要d趟分配和收集，对于n个记录的链式基数排序算法的时间复杂度为O（d（n+j）），算法不必移动记录，但每个记录需增加一个链域，共需O（n）附加空间，另外还需设置j个头、尾指针数组，因此需O（n+j）辅助空间

它适用于n较大而d娇小的情况。

[70]: /images/20220109/6f1f51e608a24347846b784e53b67a71.png