十大排序算法之桶排序

矫情吗；* 2024-04-20 09:33 76阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。  
介绍：  
在图书馆经常会有这种情况  
几十万本书，怎样才能进行快速有效的排序  
首先我们把这些书分类，一个分类代表一个桶  
当我们分好类，再进行小的分类，  
直到我们可以用简单算法进行排序的稳定状态  
思路：  
我们不知道一个分类会有多少本书，  
所以我们用数组来定义桶有些不太好用，  
最好用的工具我觉得是容器，  
每个桶都是一个容器，‘  
大桶装小桶，容器又含有内部排序的方法，  
难点：  
如何定义桶的区间范围，以及数量。  
这个，看情况而定，想订多少定多少  
![在这里插入图片描述][20190920182947681.gif]

package 日常练习;
    
    import java.util.*;
    
    public class 桶排序 {
    	public static void sort(int[] arr) {
    		//找出数组中的最大最小值，便于定义桶的大小，数量
    		int max = arr[0];
    		int min = arr[0];
    		for (int i = 0; i < arr.length; i++) {
    			max = arr[i]>max?arr[i]:max;
    			min = arr[i]<min?arr[i]:min;
    		}
    		
    		int count = (max - min) / arr.length + 1;// 桶的个数
    		ArrayList<ArrayList<Integer>> list = new ArrayList<>(count);
    		for (int i = 0; i < count; i++) {
    			list.add(new ArrayList<Integer>());
    		}
    
    		// 将每个元素放入桶
    		for (int i = 0; i < arr.length; i++) {
    			int num = (arr[i] - min) / (arr.length);
    			list.get(num).add(arr[i]);
    		}
    
    		// 对每个桶进行排序
    		for (int i = 0; i < list.size(); i++) {
    			Collections.sort(list.get(i));
    		}
    		System.out.println(list.toString());
    	}
    
    	public static void main(String[] args) {
    		int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    		sort(a);
    	}
    }

[20190920182947681.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/672380e8b4404e4db55d24147b99467b.gif