一、基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket Sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

二、算法分析

1、算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

2、过程分析

三、算法实现

package com.algorithm.tenSortingAlgorithm;

import java.util.*;

public class BucketSort {

    static final int DEFAULT_INITIAL_CAPACITY = 10; // 默认 10，这里具体看你的数据的量

    private static void bucketSort(int[] arr) {
        // 新建一个桶的集合
        ArrayList<LinkedList<Integer>> buckets = new ArrayList<LinkedList<Integer>>();
        for (int i = 0; i < DEFAULT_INITIAL_CAPACITY; i++) {
            // 新建一个桶，并将其添加到桶的集合中去。
            // 由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
            buckets.add(new LinkedList<Integer>());
        }
        // 将输入数据全部放入桶中并完成排序
        for (Integer data : arr) {
            int index = getBucketIndex(data);
            insertSort(buckets.get(index), data);
        }
        // 将桶中元素全部取出来并放入 arr 中输出
        int index = 0;
        for (LinkedList<Integer> bucket : buckets) {
            for (Integer data : bucket) {
                arr[index++] = data;
            }
        }
    }

    /**
     * 我们选择插入排序作为桶内元素排序的方法 每当有一个新元素到来时，我们都调用该方法将其插入到恰当的位置
     * @param bucket
     * @param data
     */
    private static void insertSort(List<Integer> bucket, Integer data) {
        ListIterator<Integer> iterator = bucket.listIterator();
        boolean insertFlag = true;
        while (iterator.hasNext()) {
            if (data <= iterator.next()) {
                iterator.previous(); // 把迭代器的位置偏移回上一个位置
                iterator.add(data); // 把数据插入到迭代器的当前位置
                insertFlag = false;
                break;
            }
        }
        if (insertFlag) {
            bucket.add(data); // 否则把数据插入到链表末端
        }
    }

    /**
     * 计算得到输入元素应该放到哪个桶内
     * @param data
     * @return
     */
    private static int getBucketIndex(Integer data) {
        // 这里例子写的比较简单，仅使用对10取整作为其桶的索引值
        // 实际开发中需要根据场景具体设计
        return data / DEFAULT_INITIAL_CAPACITY;
    }

    public static void main(String[] args) {
        int[] arr = {1,28,29,3,21,11,7,6,18};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

平均情况下，桶排序的时间复杂度为 O(n)。

最坏情况下，所有数据都放到同一个桶内，桶排序的时间复杂度为 O(n^2) 或 O(n * lg n)，这取决于桶内元素自排序的算法。

我们可以发现，区间划分的越细，即桶的数量越多，理论上分到每个桶中的元素就越少，桶内数据的排序就越简单，其时间复杂度就越接近于线性。

极端情况下，就是区间小到只有1，即桶内只存放一种元素，桶内的元素不再需要排序，因为它们都是相同的元素，这时桶排序差不多就和计数排序一样了。

四、十大排序算法总结

【十大排序算法】（一）冒泡排序算法
【十大排序算法】（一）冒泡排序算法（优化）
【十大排序算法】（二）快速排序算法
【十大排序算法】（三）选择排序算法
【十大排序算法】（四）堆排序算法
【十大排序算法】（五）插入排序算法
【十大排序算法】（六）希尔排序算法
【十大排序算法】（七）归并排序算法
【十大排序算法】（八）计数排序算法
【十大排序算法】（九）桶排序算法
【十大排序算法】（十）基数排序算法