数据结构之排序算法——基数排序（Java实现）

今天药忘吃喽~ 2023-03-13 06:36 2阅读 0赞

➢ **基本介绍**  
基数排序(桶排序)介绍:

1.  基数排序(radixsort)属于“分配式排序”( distributionsort)，又称“桶子法”( bucket sort)或binsort, 顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2.  基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3.  基数排序(Radix Sort)是桶排序的扩展
4.  基数排序是1887年赫尔曼何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较。

➢ **基本思想**  
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直 到最高位排序完成以后,数列就变成一个有序序列。

第1轮排序:

1.  将每个元素的个位数取出，然后看这个数应该放在哪个对应的桶(一个一维数组)
2.  按照这个桶的顺序(-维数组的下标依次取出数据，放入原来数组)

第2轮排序:

1.  将每个元素的十位数取出，然后看这个数应该放在哪个对应的桶(一个一维数组)
2.  按照这个桶的顺序(-维数组的下标依次取出数据，放入原来数组)

。。。。。。依次类推

➢**思路图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
➢**代码实现：**  
第一轮的运行代码：在后续我们只需要修改获取不同位数的值即可。第二轮获取十位数，第三轮获取百位数。

// 定义二维数组表示十个桶
    		int[][] bucket = new int[10][arr.length];
    		// 定义一个一维数组，记录放入桶中的元素有多少个。
    		int[] bucketelem = new int[10];
    		// 第一轮：针对个位数进行排序
    		for (int j = 0; j < arr.length; j++) { 
    			// 取出个位
    			int digit = arr[j] % 10;
    			// 放入桶中
    			bucket[digit][bucketelem[digit]] = arr[j];
    			bucketelem[digit]++;
    		}
    		// 把元素返回到原来数组
    		int index = 0;
    		for (int k = 0; k < bucket.length; k++) { 
    			// 如果桶中有数据，放回原数组
    			if (bucketelem[k] != 0) { 
    				for (int l = 0; l < bucketelem[k]; l++) { 
    					arr[index] = bucket[k][l];
    					index++;
    				}
    			}
    			// 第一轮处理后，清空bucketelem[k]=0
    			bucketelem[k] = 0;
    		}

总体代码如下：

public static void base(int[] arr) { 
    		// 定义二维数组表示十个桶
    		int[][] bucket = new int[10][arr.length];
    		// 定义一个一维数组，记录放入桶中的元素有多少个。
    		int[] bucketelem = new int[10];
    		// 得到最大的位数
    		int max = arr[0];
    		for (int i = 1; i < arr.length; i++) { 
    			if (arr[i] > max) { 
    				max = arr[i];
    			}
    		}
    		// 判断max是几位数
    		int maxlength = (max + "").length();
    		// 第一轮：针对个位数进行排序
    		for (int i = 0, n = 1; i < maxlength; i++, n *= 10) { 
    			for (int j = 0; j < arr.length; j++) { 
    				int digit = arr[j] / n % 10;
    				// 放入桶中
    				bucket[digit][bucketelem[digit]] = arr[j];
    				bucketelem[digit]++;
    			}
    
    			// 把元素返回到原来数组
    			int index = 0;
    			for (int k = 0; k < bucketelem.length; k++) { 
    				// 如果桶中有数据，放回原数组
    				if (bucketelem[k] != 0) { 
    					for (int l = 0; l < bucketelem[k]; l++) { 
    						arr[index++] = bucket[k][l];
    					}
    				}
    				// 处理后，清空bucketelem[k]=0
    				bucketelem[k] = 0;
    			}
    		}
    	}

调用方法进行测试：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
➢**测试代码的效率**  
参考前文：[**https://blog.csdn.net/qq\_44973159/article/details/106071569**][https_blog.csdn.net_qq_44973159_article_details_106071569] 使用最后的测试效率的代码进行测试，在测试10000000个数据。：基本在1-2秒之间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
但是存在的问题是，使用基数排序的时候会太消耗空间。如下所示：当在原先的基础上再加俩个零，将会报错：java.lang.OutOfMemoryError: Java heap space 堆内存不足。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/465ce18f4c63452e9d73aef69c1512c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230312/4740e95661924ab98d9e5d9300d654de.png
[https_blog.csdn.net_qq_44973159_article_details_106071569]: https://blog.csdn.net/qq_44973159/article/details/106071569
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: /images/20230312/a457720cd11b49b8a3d7bf0bfb2895d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]: /images/20230312/9613276149fa4040989d57a85015f12f.png