排序之桶排序

package com.zhang.reflection.面试.排序;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
public class 桶排序 {
    public static int[] bucketSort(int[] arr) {
        //得到数列的最大值和最小值，并计算出差值d
        int max=arr[0];
        int min=arr[0];
        for(int i=1;i<arr.length;i++) {
            if(arr[i]>max) {
                max=arr[i];
            }
            if(arr[i]<min) {
                min=arr[i];
            }
        }
        int d=max-min;
        //初始化桶
        int bucketNum=arr.length;
        ArrayList<LinkedList<Integer>> bucketList=new ArrayList<LinkedList<Integer>>(bucketNum);
        for(int i=0;i<bucketNum;i++) {
            bucketList.add(new LinkedList<Integer>());
        }
        //遍历原始数组将每个元素放入桶中
        for(int i=0;i<arr.length;i++) {
            int num=(arr[i]-min)*(bucketNum-1)/d;
            bucketList.get(num).add(arr[i]);
        }

        //对每个桶内部进行排序
        for(int i=0;i<bucketList.size();i++) {
            //使用Collections.sort，其底层实现基于归并排序或归并排序的优化版本
            Collections.sort(bucketList.get(i));
        }
        //输出全部元素
        int[] sortedArray=new int[arr.length];
        int index=0;
        for(LinkedList<Integer> list:bucketList) {
            for(int element:list) {
                sortedArray[index]=element;
                index++;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        int[] result=bucketSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }
}