java面经查缺补漏之四十天（今天来补充几个算法计数排序，桶排序）

柔情只为你懂 2023-07-24 11:54 2阅读 0赞

**1.计数排序（桶排序的特殊情况，只是每个桶只有一个数）**

用于那些数字比较集中的，并且在一定范围内的，其实就是用hash数组先记录一下次数而已

public static void jishusort(int[] array)
        {
            int max=Integer.MIN_VALUE;
            int min=Integer.MAX_VALUE;
            for(int x:array)
            {
                max=Math.max(max,x);
                min=Math.min(min,x);
            }
            int[] count=new int[max-min+1];
            for(int x:array)
            {
                count[x-min]++;
            }
            int index=0;
            for(int i=0;i<count.length;i++)
            {
                while(count[i]>0)
                {
                    array[index]=i+min;
                    index++;
                    count[i]--;
                }
            }
        }

2.桶排序

桶排序可用于最大最小值相差较大的数据情况，把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。

public static void bucketSort(int[] arr){
    	
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        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]);
        }
    	
        //对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
    	
        System.out.println(bucketArr.toString());
    	
    }