桶排序

桶排序是针对类似这样的情况:
有N个整数, 它们的范围是$[0, M]$[0,M], 那么我们可以做(伪码描述):

• 初始化一个count数组(也就是所谓的桶), 长度为M+1, 每个元素为一个空链表
  这里用链表, 主要是当有重复元素时保持插入操作的快速;
• 依次读入N个整数, 将arr[i]插入到count[arr[i]]这个链表中;
• 从0到M, 如果桶count[i]不为空(链表size()大于0), 依次输出;

下面是用c++演示的例子:

#include <iostream>
#include <vector>
#include <list>

using namespace std;
const int M = 10; // 待排数组中元素最大值

vector<int> bucket_sort(int arr[], int N) {
    // 声明count数组, 包含M+1个桶, 每个桶初始为一个空链表
    vector<list<int>> count(M + 1);
    vector<int> result;
    int i;

    // 将N个数据放入桶中
    for (i = 0; i < N; i++) {
        count[arr[i]].push_front(arr[i]);
    }

    // 输出所有桶中的数据, 这里是放到一个vector中然后返回出去
    for (i = 0; i < M + 1; i++) {
        list<int> tmp = count[i];
        if (tmp.size() > 0) { // 如果某个桶不为空, 输入桶中所有元素
            for (list<int>::iterator iter = tmp.begin(); iter != tmp.end(); iter++) {
                result.push_back(*iter);
            }
        }
    }
    return result;
}

上面的例子只说明了桶排序的思想, 是数据连续的情况.
如果不连续, 如: int arr2[] = {77, 99, 35, 22, 3, 100, 8, 3, 5, 4, 1, 0}; 这种的呢?
按上面的做法需要101个桶, 显然这是非常浪费的.
可以只给10个桶, 数据按照0-9, 10-19, …, 80-89, 90-100来放入不同的桶中.
然后每个桶中的数据在插入时保持有序, 最后合并这10个桶.
c++代码简单实现如下:

// 按`0-9`, `10-19`, .., `80-89`, `90-100`来分类
vector<int> bucket_sort2(int arr[], int N) {
    const int bucketNum = 10; // 桶个数
    vector<list<int>> count(bucketNum);
    vector<int> result;
    list<int> tmp;
    int i;

    for (i = 0; i < N; i++) {
        int bucketIndex = arr[i] / 10;
        if (bucketIndex > 9) { // arr[i] == 100
            bucketIndex = 9;
        }

        // 放入桶内, 并将相应桶中元素排序
        count[bucketIndex].push_front(arr[i]);
        count[bucketIndex].sort();
    }

    // 合并桶
    for (i = 0; i < bucketNum; i++) {
        tmp = count[i];
        if (tmp.size() > 0) { // 如果某个桶不为空, 输入桶中所有元素
            for (list<int>::iterator iter = tmp.begin(); iter != tmp.end(); iter++) {
                result.push_back(*iter);
            }
        }
    }

    return result;
}

测试程序:

int main(int argc, char *argv[])
{
    int arr[] = {10, 9, 8, 3, 5, 4, 1, 2, 0, 7, 6, 9, 5, 4, 9};
    vector<int> result = bucket_sort(arr, sizeof(arr) / sizeof(int));

    // 0 1 2 3 4 4 5 5 6 7 8 9 9 9 10
    for (vector<int>::iterator iter = result.begin(); iter != result.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;

    int arr2[] = {77, 99, 35, 22, 3, 100, 8, 3, 5, 4, 1, 0};
    vector<int> result2 = bucket_sort2(arr2, sizeof(arr2) / sizeof(int));
    // 0 1 3 3 4 5 8 22 35 77 99 100
    for (vector<int>::iterator iter = result2.begin(); iter != result2.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
    return 0;
}

完整代码在这里

欢迎补充指正!