桶排序

    桶排序最好、平均、最坏情况都是O(n)。

    给定n个元素的集合，桶排序构造n个桶来切分输入集合，因此桶排序能够降低其处理时其在额外空间的开销。如果一个散列函数，hash(A[i])，用来均匀的将n个元素分配到n个桶中，那么桶排序在最坏的情况下也能够以O(n)的时间进行排序。如果希望使用桶排序，需要满足以下两点:

• 均匀分布：输入数据需要均匀分布在一个给定的范围。基于这种分配，算法创建n个桶来平分输入数据；
• 有序散列函数：桶必须是有序的。也就是说，如果i

    一旦所有待排序的元素都已经放入桶中，桶排序从左至右对每个桶中的值使用插入排序。每个桶中的元素按照顺序从左至右抽取出来重新构成数组，此时的数组为有序数组。

    使用环境：待排序元素能够使用一个快速散列函数均匀分配时，桶排序是最快的排序法。当元素是从一个密集集合中抽取出来的，应选择桶排序。

    桶也能够使用固定大小的数组来存储，当桶满后，数组可以重新分配空间，但是链表实现要快30%~40%
在n个桶上执行插入排序的总开销加起来，总的期望性能为O(n)。

sort(A)
    create n buckets B
    for i=0 to n-1 do
        k = hash(A[i])
        add A[i] to the k bucket B[k]
    extract(B, A)
end

extract(B, A)
    idx = 0
    for i=0 to n-1 do
        insertionSort(B[i])
        for m=1 to size(B[i]) do
            A[idx++] = the m element of B[i]
end

C语言实现：

extern int hash(void *elt);                    //快速散列函数
extern int numBuckets(int numElements);        //根据元素的总数，计算需要桶的数目

//桶中元素链表
typedef struct entry
{
    void            *element;
    struct entry    *next;
}ENTRY;

//维护每个桶中元素的数目，并且指向第一个元素
typedef struct bucket
{
    int        size;
    ENTRY    *head;
}BUCKET;

//桶的指针，以及桶的数量
static BUCKET *buckets = 0;
static int num = 0;

//一个接一个移除，并且覆盖数组arr
void extract(
    BUCKET *buckets,
    int(*cmp)(const void *, const void *),
    void **arr, int n)
{
    int i, low;
    int idx = 0;
    for(i=0; i    {
        ENTRY *ptr = NULL;
        ENTRY *tmp = NULL;

        ptr = buckets[i].head;
        if(buckets[i].size == 1)
        {
            arr[idx++] = ptr->element;
            free(ptr);
            buckets->size = 0;
            continue;
        }

        low = idx;
        arr[idx++] = ptr->element;
        tmp = ptr;
        ptr = ptr->next;
        free(tmp);

        //对链表中的元素执行插入排序，然后插入到数组中，然后释放链表。
        while(NULL != ptr)
        {
            int i =idx-1;
            while(i>=low && cmp(arr[i], ptr->element) >0)
            {
                arr[i+1] = arr[i];
                i--;
            }

            arr[i+1] = ptr->element;
            tmp = ptr;
            ptr = ptr->next;
            free(tmp);
            idx++;
        }

        buckets[i].size = 0;
    }
}

void SortPointers(void **arr, int n,
                  int(*cmp)(const void *, const void *))
{
    int i;
    num = numBuckets(n);
    buckets = (BUCKET *)calloc(num, sizeof(BUCKET));
    for(i=0; i    {
        int k = hash(arr[i]);
        ENTRY *e = (ENTRY *)calloc(1, sizeof(ENTRY));
        e->element = arr[i];
        if(NULL == buckets[k].head)
        {
            buckets[k].head = e;
        }
        else
        {
            e->next = buckets[k].head;
            buckets[k].head = e;
        }

        buckets[k].size++;
    }

    //读取并覆盖arr。
    extract(buckets, cmp, arr, n);
    free(buckets);
}

参考：《算法技术手册》