[数据结构与算法]排序算法：桶排序（java实现）

桶排序是计数排序的升级版。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。桶排序利用了函数的映射关系把数据分配到桶里，高效与否的关键就在于这个映射函数的确定。

算法思路

• 根据待排序集合中的数据，确定映射规则和桶的数量；
• 遍历待排序集合，将每一个元素根据映射规则，移动到对应的桶中；
• 对每一个桶中元素进行排序。
  *依次输出每个桶中的数据，得到整个有序的集合。

步骤：
1.找出待排序数组中的最大值max、最小值min
2.桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶存放桶的下标=(arr[i]-min)/arr.lengh
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组

在这里插入代码片import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BucketSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	    bucketSort(arr);
	    System.out.println(Arrays.toString(arr));
	}
	public static void bucketSort(int[] a) {
		int max = a[0];
		int min = a[0];
		for(int i=0; i<a.length; i++) {
			if(a[i]<min) {
				min = a[i];
			}
			if(a[i]>max) {
				max = a[i];
			}
		}
		int count = (max-min)/a.length+1;
		ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
		for(int i=0;i<count;i++) {
			lists.add(new ArrayList<Integer>());
		}
		for(int i=0; i<a.length; i++) {
			lists.get((a[i]-min)/a.length).add(a[i]);
		}
		int k = 0;
		for(int i=0; i<lists.size(); i++) {
			Collections.sort(lists.get(i));
		}
		for(int i=0; i<lists.size(); i++) {
			ArrayList<Integer> bucket = lists.get(i);
			for(int j = 0; j<bucket.size(); j++) {
				a[k++] = bucket.get(j);
			}
		}
	}
}