十大经典排序算法-桶排序

编程算法

发布日期: 2020-12-09

文章字数: 890

阅读时长: 3 分

前言

本文重点讲解十大经典排序算法的桶排序

要点

桶排序（Bucket sort）或所谓的箱排序，是一个平均情况下以线性时间运行的排序算法。
工作的原理是将数组分到有限数量的桶子里，每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
桶排序是鸽巢排序的一种归纳结果，当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间$O(n)$，但桶排序并不是比较排序，他不受到$O(nlogn)$下限的影响。
在十大排序算法中基数排序和计数排序都可以看作是桶排序。

计数排序：当桶的个数取最大（maxV-minV+1）的时候，就变成了计数排序。
基数排序：桶排序是按值区间划分桶，基数排序是按数位来划分，基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。

基本思想

将待排序元素划分到不同的桶。
先扫描一遍序列求出最大值maxV和最小值minV，设桶的个数为k，则把区间[minV, maxV]均匀划分成k个区间，每个区间就是一个桶。
将序列中的元素分配到各自的桶，对每个桶内的元素进行排序，可以选择任意一种排序算法，将各个桶中的元素合并成一个大的有序序列。

代码实现

以下代码由java实现

public class BucketSort {

    /**
     * 桶排序
     * @param arr
     * @return
     */
    public static double[] sort(double[] arr) {
        if (arr.length <= 0) {
            return null;
        }
        //得到数列的最大值和最小值，并算出差值d
        double max = arr[0];
        double 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];
            }
        }
        double d = max - min;
        //初始化桶
        int bucketNum = arr.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }
        //遍历原始数组，将每个元素放入桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (int) ((arr[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(arr[i]);
        }
        //对每个桶内部进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            //JDK底层采用了快速排序和优化的归并排序
            Collections.sort(bucketList.get(i));
        }
        //输出全部元素
        double[] sortedArray = new double[arr.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[] arr = {9.22, 5.11, 3.2, 6.02, 8.5, 1.12, 2.33, 3.23, 11.34, 52.6, 32.9, 11.8, 23.7};
        System.out.println(Arrays.toString(sort(arr)));
    }
}

时间性能

假设数据是均匀分布的，则每个桶的元素平均个数为n/k，假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为：$O(n/klog(n/k))$。
总的时间复杂度为：$O(n)+O(k)O(n/klog(n/k))=O(n+nlog(n/k))=O(n+nlogn-nlogk)$。
当k接近于n时，桶排序的时间复杂度就可以认为是$O(n)$的，即桶越多，时间效率就越高，而桶越多，空间就越大。