十大排序算法之基数排序

左手的ㄟ右手 2024-04-20 09:43 12阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。

介绍：  
其实基数排序被讲得有些复杂了，很多人对于它的原理不明觉历。  
包括我本人，思考了很久才有些理解，不过也不知道是否正确  
从基数比较难以理解，  
可以先从最高位开始理解

思路：  
如果有两个数，他们同时除以1000，  
则剩下的数大的在右边，小的在左边  
如果剩下的数相等，则把他们摞在一起，  
再把每一个数除以100，小的往左挤一挤，大的往右挤一挤  
类推之后实现排序。  
反之则是基数排序。

难点：  
如何将尾数相同的元素摞在一起  
定义二维数组，10\*n；  
会产生空间浪费，不过不可避免。。  
![在这里插入图片描述][2019092019015360.gif]

package 日常练习;
    
    import java.util.Arrays;
    
    public class 基数排序 {
    	public static int arr[] = { 3, 44, 34, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	private static void Sort() {
    		int n = 1;// 代表位数对应的数：1,10,100...
    		int k = 0;// 保存每一位排序后的结果用于下一位的排序输入
    		int len = arr.length;
    		int[][] quer = new int[10][len];// 排序矩阵用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个行里
    		int[] count = new int[len];// 用于保存每个行里有多少个数字
    		int max=arr[0];
    		for (int i = 0; i < arr.length; i++) {
    			max = arr[i]>max?arr[i]:max;
    		}
    		while (n < max*10) {  
    			for (int i=0; i<arr.length;i++) // 将数组arr里的每个数字放在相应的行里
    			{
    				int tail= (arr[i]/ n) % 10;
    				quer[tail][count[tail]] =arr[i];
    				count[tail]++;
    			}
    			for (int i = 0; i < len; i++)// 将前一个循环生成的矩阵里的数据覆盖到原数组中用于保存这一位的排序结果
    			{
    				if (count[i] != 0)// 这个行里有数据，从上到下遍历这个行并将数据保存到原数组中
    				{
    					for (int j = 0; j < count[i]; j++) {
    						arr[k] = quer[i][j];
    						k++;
    					}
    				}
    				count[i] = 0;// 将行的计数器置0，用于下一次位排序
    			}
    			n *= 10;
    			k = 0;// 将k置0，用于下一轮保存位排序结果
    		}
    	}
    	public static void main(String[] args) {
    		Sort();
    		System.out.println(Arrays.toString(arr));
    	}
    }

[2019092019015360.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5a9bc323345749f3b2c4d594dd1c3429.gif