排序算法——桶排序

「爱情、让人受尽委屈。」 2022-12-23 12:27 186阅读 0赞

# 排序算法——桶排序 #

> 桶排序的工作原理是将数组分到有限数量的桶里，每个桶再分别排序。桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的(arr\[i\]-min)/(arr.length)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做比较排序即可。

例如一组数组\{99,88,77,66,55,44,33,22,11\}，先计算出桶数(max-min)/arr.length+1=(99-11)/9+1≈10.778，截取整数部分(不进行四舍五入)，得出共有10个桶；再将数组的每个数放到第(int)(arr\[i\]-min)/(arr.length)-1个桶中，例如：99放到第(int)(99-11)/9+1=10个桶，88放到第(int)(88-11)/9+1=9个桶，77放到第(int)(77-11)/9+1=8个桶，以此类推；此时分别有10个桶分别为\[11\]、\[22\]、\[33\]、\[44\]、\[55\]、\[\]、\[66\]、\[77\]、\[88\]和\[99\]，最后对每个桶的数据排序得到\{11,22,33,44,55,66,77,88,99\}。

###### Java代码实现： ######

> 注：需导入java.util中的ArrayList、Collections。

import java.util.ArrayList;
    import java.util.Collections;

public static void main(String[] args) { 
    	int[] arr = { 99,88,77,66,55,44,33,22,11}; 
    	bucketSort(arr);//桶排序
    }
    public static void bucketSort(int[] arr)//桶排序
    { 
    	int max = Integer.MIN_VALUE;//int最小值：-2^31=-2147483648
    	int min = Integer.MAX_VALUE;//int最大值：(2^31)-1=2147483647
    	for(int i = 0; i < arr.length; i++){ 
    		max = Math.max(max, arr[i]);//取数组最大值
    		min = Math.min(min, arr[i]);//取数组最小值
    	}
    	int bucketNum = (max - min) / arr.length + 1;//桶数
    	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>	(bucketNum);
    	for(int i = 0; i < bucketNum; i++){ 
    		bucketArr.add(new ArrayList<Integer>());
    	}
    	//将每个元素放入桶
    	for(int i = 0; i < arr.length; i++){ 
    		int num = (arr[i] - min) / (arr.length);
    		bucketArr.get(num).add(arr[i]);
    	}
    	System.out.println("共"+bucketArr.size()+"个桶："+bucketArr.toString());
    	//对每个桶进行排序
    	for(int i = 0; i < bucketArr.size(); i++){ 
    		Collections.sort(bucketArr.get(i));
    	}
    	System.out.println("已排序的桶："+bucketArr.toString());
    	ArrayList <Integer> a = new ArrayList<Integer>();//用作存放每个桶的元素
    	for (ArrayList<Integer> arrayList : bucketArr) { 
    		for (int i : arrayList) { 
    			a.add(i);//所有桶的元素依次放入集合中
    		}
    	}
    	for (int i = 0; i < a.size(); i++) { 
    		arr[i]=a.get(i);//a集合的元素依次赋给原数组
    	}
    	System.out.print("桶排序结果：");
    	for (int l : arr) { 
    		System.out.print(l+",");
    	}
    }

###### 执行结果： ######

![在这里插入图片描述][20201125103252866.png_pic_center]

[20201125103252866.png_pic_center]: /images/20221120/731dd91c3c7042179b2d31cd4b57d44b.png