排序算法-桶排序

川长思鸟来 2022-10-18 12:42 172阅读 0赞

先创建若干个桶，每个桶存放不同范围的数据  
桶和桶之间的跨度=(数据最大值-数据最小值)/ (桶的数量 - 1)

假设有一个数组：1.2，0.5，4.5，2.6，2.7  
这里如果桶数量等于原始数列的元素数量  
跨度=(4.5-0.5)/(5-1)=1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70]

然后将数据投入对应的桶中  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70 1]

再对桶内的数据排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70 2]  
代码实现

public class BucketSort {
        
        public static double[] bucketSort(double[] array) {
        
            double max = 0;
            double min = 0;
            //获得最大值和最小值之间的差
            for (int i = 0; i < array.length; i++) {
        
                if (array[i] > max) {
        
                    max = array[i];
                }
                if (array[i] < min) {
        
                    min = array[i];
                }
            }
            double d = max - min;
            //桶初始化
            int bucketNum = array.length;
            ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
            for (int i = 0; i < bucketNum; i++) {
        
                bucketList.add(new LinkedList<>());
            }
            //将每个元素放入桶中
            for (int i = 0; i < array.length; i++) {
        
                //(array[i] - min)/ ((max - min)/(bucketNum - 1))
                int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
                bucketList.get(num).add(array[i]);
            }
            //对每个桶内部进行排序
            for (int i = 0; i < bucketList.size(); i++) {
        
                Collections.sort(bucketList.get(i));
            }
            //输出全部元素
            double[] sortedArray = new double[array.length];
            int index = 0;
            for (LinkedList<Double> list : bucketList) {
        
                for (double element : list) {
        
                    sortedArray[index] = element;
                    index++;
                }
            }
            return sortedArray;
        }
    
        public static void main(String[] args) {
        
            double[] array = {
        4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
            double[] sortedArray = bucketSort(array);
            System.out.println(Arrays.toString(sortedArray));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70]: /images/20221005/041f37a2e354418a9cd0f77deb6a9b3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70 1]: /images/20221005/2afb5dbfbc944beb91d2a828ef7c9661.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTAyOTI4Ng_size_16_color_FFFFFF_t_70 2]: /images/20221005/35970e225c4d4bd4b8b9817499cfeab5.png