【高级排序】之桶排序

灰太狼 2022-02-04 22:57 212阅读 0赞

### 算法评价： ###

**时间复杂度：O(N)。N为待排序元素的个数。**

注：前提是数据服从均匀分布，它的平均时间复杂度才为O(N)。

注：时间复杂度实际为![20190503190454800.png][]，再通过一些列化简后，可得到O(N)的时间复杂度，具体化简  
       过程可详见《算法导论》。

注：即使输入数据不服从均匀分布，桶排序也仍然可以在线性时间内完成。只要输入数据满足下列性质:所有桶的  
       大小（即：桶内元素的个数)的平方和与总的被排序元素个数呈线性关系。此结论的理论公式是：  
      ![20190503190518161.png][]，其中n表示总的被排序元素的个数，![2019050319054942.png][]表示桶B\[i\]中元素的个数。

**空间复杂度：O(M + N)。其中，M为桶的个数，N为待排序元素的个数。**

**稳定性：稳定。**

**适用数据：服从均匀分布的数据。**

### 说明： ###

*  桶排序算法是以空间换时间的算法，是最快的算法。不过其适用范围有局限性。
 *  对于那些(可以通过偏移、缩放等技巧处理后)服从均匀分布、数据跨度不大的数据，可以按照一个桶对应一个数据的思路，进行程序设计。以数组索引位置对应元素值，操作值就变成了操作索引下标，所以速度会很快，不过比较占空间资源。
 *  对于真正的桶排序，一个桶对应一个范围的数据，桶的数量可以小于被排序元素的跨度范围。不过个人感觉此情况下的桶排序性能上略差，使用桶排序意义不大。

### (一个桶对应一个数据范围的)桶排序算法演示图： ###

![20190503190746289.gif][]

### 桶排序工具类： ###

**声明：真正的桶排序工具类不好写，本人也没写，桶排序虽然快，但是适用范围局限性还是挺大的，所以这  
           里只给出了一个对那些(可以通过偏移、缩放等技巧处理后)服从均匀分布、数据跨度不大的整数数据  
           进行桶排序的工具类。**

/**
     * 桶排序的Java实现
     *
     * @author JustryDeng
     * @date 2019/5/2 13:17
     */
    public class Bucket {
    
        /**
         * 桶排序的简单实现
         * 注意: 1、此方法仅适用于整数(正整数、0、负整数)
         *      2、此方法适用于 待排序元素之间 跨度不大的数组，如: [-100, -90, -60, -40, -10, 0, 1, 3, 5, 10, 23, 40]等
         *      3、此方法不适用于元素值间跨度较大的数组， 如: 不适用于[1, 10000, 100000000], 因为在
         *        代码中动态创建的【桶的个数 = 最大元素值 - 最小元素值 + 1】，所以如果跨度太大的话，可能导致OOM错误
         *
         * P.S.其实对于数组的排序，我们可以考虑使用Arrays.sort();来实现，不过Arrays.sort()采用的是快速排序，而非桶排序
         *
         * @param array
         *            待排序数组
         * @param asc
         *            升序/降序, true-升序,false-降序
         * @return  排好序了的数组
         * @date 2019/5/3 2:54
         */
        public static int[] sort(int[] array, boolean asc){
            if (array == null || array.length <= 1) {
                return array;
            }
            // -> 非必须辅助逻辑
            // 若数组中存在负数，则将数组元素值进行偏移，获得非负数组
            int minValue = getMinOrMaxValue(array, true);
            if (minValue != 0) {
                for (int i = 0; i < array.length; i++) {
                    array[i] -= minValue;
                }
            }
            // 根据最大元素的值，设置桶的个数
            int maxValue = getMinOrMaxValue(array, false);
            int[] bucketArray = new int[maxValue + 1];
    
            // -> 桶排序实现逻辑
            for (int value : array) {
                bucketArray[value]++;
            }
            int index = asc ? 0 : array.length - 1;
            int ascFlag = asc ? 1 : -1;
            for (int i = 0; i < bucketArray.length; i++) {
                for (int j = 0; j < bucketArray[i]; j++) {
                    array[index] = i + minValue;
                    index = index + ascFlag;
                }
            }
            return array;
        }
    
        /**
         * 获取数组中的最小值/最大值
         *
         * @param array
         *            待排序数组
         * @return  min
         *             是否获取最小值， true-获取最小值，false-获取最大值
         * @date 2019/5/3 2:53
         */
        private static int getMinOrMaxValue(int[] array, boolean min){
            int mostValue = array[0];
            for (int value : array) {
                if (min && mostValue > value) {
                    mostValue = value;
                    continue;
                }
                if (!min && mostValue < value) {
                    mostValue = value;
                }
            }
            return mostValue;
        }
    
    }

### 测试一下： ###

**测试一：**

![2019050319152471.png][]

控制台输出：

![20190503191536572.png][]

**测试二：**

![20190503191549961.png][]

控制台输出：

![20190503191617397.png][]

**由此可见，****(适用于整数的)桶****排序工具类编写成功****！**

**笔者寄语：本人感觉此篇博客还有待完善的地方，不过暂时不知道从哪方面进行完善，请朋友们指点。**

### ^\_^ 如有不当之处，欢迎指正 ###

### ^\_^ 参考书籍                 《算法导论》Thomas H.Cormen Charles E.Leiserson                   Ronald L.Rivest Clifford Stein 著 殷建平 徐云 王刚                   刘晓光 苏朋 邹恒明 王宏志 译 ###

### ^\_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng ###

[20190503190454800.png]: /images/20220205/5a074b3eb94d422297bed041ee4901c6.png
[20190503190518161.png]: https://img-blog.csdnimg.cn/20190503190518161.png
[2019050319054942.png]: /images/20220205/e61ba863a7364dcb8ff92d7ad3436442.png
[20190503190746289.gif]: /images/20220205/f92cc55ee23f4706b8bbc96f04fb4366.png
[2019050319152471.png]: /images/20220205/f52b32900a9d4a3196295885aec31cd1.png
[20190503191536572.png]: /images/20220205/64d31e28b8b5413d8ce64a628164fba2.png
[20190503191549961.png]: /images/20220205/31856bc593794d849eae39259e17fa17.png
[20190503191617397.png]: /images/20220205/7923e63d7854488dbcf69ec596795bc1.png