排序 - 桶排序（7）

旧城等待， 2022-01-05 07:47 274阅读 0赞

**概念**

桶排序 (Bucket sort)或所谓的箱排序，桶排序是鸽巢排序的一种归纳结果。但桶排序并不是 比较排序，它不受到 O(n log n) 下限的影响。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1.  在额外空间充足的情况下，尽量增大桶的数量
2.  使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

**实现原理**

工作的原理是将数组分到有限数量的桶子里。每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

**排序演示**

元素分布在桶中：

![Bucket_sort_1.svg_.png][]

然后，元素在每个桶中排序：

![Bucket_sort_2.svg_.png][]

**代码实现**

public static double[] bucketSort(double[] array) {
    		//第一步：找出待排序的数组中最大和最小的元素
    		double max=array[0];
    		double min=array[0];
    		for(double i:array){
    			if(i>max){
    				max=i;
                            }
    			if(i<min){
                                min=i;
                            }
    		}
    
    		double d=max-min;
    		//第二步：初始化桶
    		int bucketNum=array.length;
    		ArrayList<LinkedList<Double>> bucketList=new ArrayList<LinkedList<Double>>();
    		for(int i=0;i<bucketNum;i++) {
    			bucketList.add(new LinkedList<Double>());
    		}
    		//第三步：遍历原始数组，将每个元素放入桶中
    		for(int i=0;i<array.length;i++) {
    			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[] sortArray=new double[array.length];
    		int index=0;
    		for(LinkedList<Double> list:bucketList) {
    			for(double element:list) {
    				sortArray[index]=element;
    				index++;
    			}
    		}
    		return sortArray;
    	}

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList<Double>），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：

**(array\[i\] - min)  \* (bucketNum-1) / d**

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。

**算法分析**

*  时间复杂度
    
     *  理想情况下，当要被排序的数组内的元素是均匀分配的时候，桶排序使用线性时间（O（n））。
     *  极端情况下，当要被排序的数组内的元素极不均匀的时候，第一个桶有n-1个元素，最后一个桶有1个元素，此时的时间复杂度将会退化到O（n log n），还白白创建了许多空桶。
     *  上面代码的时间复杂度，假设原始数列有n个元素，分成m个桶（我们采用的分桶方式 m=n），平均每个桶的元素个数为n/m。  
        下面我们来逐步分析算法复杂度：  
        第一步求数列最大最小值，运算量为n。  
        第二步创建空桶，运算量为m。  
        第三步遍历原始数列，运算量为n。  
        第四步在每个桶内部做排序，由于使用了O（nlogn）的排序算法，所以运算量为 n/m \* log(n/m ) \* m。  
        第五步输出排序数列，运算量为n。  
        加起来，总的运算量为 3n+m+ n/m \* log(n/m ) \* m = 3n+m+n(logn-logm) 。  
        去掉系数，时间复杂度为：**O(n+m+n(logn-logm)）**
 *  空间复杂度  
    空桶占用的空间 + 数列在桶中占用的空间 = **O（m+n）**。
 *  算法稳定性  
    桶排序是稳定的

**使用场景**

1.  当输入的数据可以均匀的分配到每一个桶中的时候，适合桶排序，同时也最快。
2.  当输入的数据被分配到了同一个桶中的时候，不适合桶排序，同时也最慢。
3.  桶排序非常快，但是同时也非常耗空间，基本上是最耗空间的一种排序算法

[Bucket_sort_1.svg_.png]: /images/20211229/24090af80b7b4e2fa4de9332bb132dfd.png
[Bucket_sort_2.svg_.png]: /images/20211229/5cdcaf57074a4b5ab2f984594ccecb21.png