主要内容 #

1. 算法讲解
2. 例程
3. 复杂度分析

1. 算法讲解 #

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

1.1 计算步骤 #

一般来说，具体算法描述如下：

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

1.2过程模拟 #

原始数据：  1 1 5 2 6 9 3 4 1 5 4 4 9 3 6 4 7 6 8 
排序结果：
0号桶  0（个数据）
1号桶  3（个数据）
2号桶  1（个数据）
3号桶  2（个数据）
4号桶  4（个数据）
5号桶  2（个数据）
6号桶  2（个数据）
7号桶  1（个数据）
8号桶  1（个数据）
9号桶  1（个数据）
按照有序桶的顺序输出结果。

元素分配到桶中

对桶中元素排序

2. 例程 #

示例程序：

#include < iostream >
using namespace std;
const int NUM_BIN = 10; // number of bins.

int main()
{
    int a[] = { 1, 1, 5, 2, 6, 9, 3, 4, 1, 5, 4, 4, 9, 3, 6, 4, 7, 6, 8 };
    int b[NUM_BIN] = { 0 };

    int n = sizeof(a) / sizeof(int);
    for (int i = 0; i < n; ++i)
        b[a[i]]++;

    for (int i = 0; i <= NUM_BIN; ++i)
    {
        while (b[i] > 0)
        {
            cout << i << " ";
            b[i]--;
        }
    }

    return 0;
}

3. 复杂度分析 #

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O(n)）。

习题 #

请默写上述代码。