桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

示意图

image

然后，元素在每个桶中排序：

image

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//链表节点
struct bucketitem{
    int index;
    int data;
    struct bucketitem* next;
};
//桶排序
void bucket_sort(int a[],int len){
    int maxvalue=a[0],minvalue=a[0];
    for(int x=0;x<len;x++){
        maxvalue=a[x]>maxvalue?a[x]:maxvalue;
        minvalue=a[x]<minvalue?a[x]:minvalue;
    }
    //获取每个桶容量
    int bucketsize=(maxvalue-minvalue)/len+1;
    //获取桶数量
    int bucketcount=(maxvalue-minvalue)/bucketsize+1;
    struct bucketitem buckets[bucketcount];
    //初始化链表头
    for(int i=0;i<bucketcount;i++){
        struct bucketitem item={-1,0,NULL};
        //每个桶链表的表头不存数据，统一设置为标识表头
        buckets[i]=item;
    }
    //放置临时分配的内存地址
    int m[len];
    for(int i=0;i<len;i++){
        //算出a[i]对应的桶位置
        int pos=(a[i]-minvalue)/bucketsize;
        //新建链表节点并赋值
        struct bucketitem* item=(struct bucketitem*) malloc(sizeof(struct bucketitem));
        item->index=i;
        item->data=a[i];
        item->next=NULL;
        //将新节点推入pos位置链表
        link_push(&buckets[pos],item);
        m[i]=item;
    }
    print_range(a,len,buckets);
    int k=0;
    //从小到大遍历桶位置，并把桶中排序好的元素取出赋值给a数组
    for(int i=0;i<bucketcount;i++){
        struct bucketitem* cur=buckets[i].next;
        while(cur!=NULL){
            a[k++]=cur->data;
            cur=cur->next;
        }
    }
    //释放内存
    for(int i=0;i<len;i++){
        free(m[i]);
    }
}
//推入链表合适位置
void link_push(struct bucketitem* src,struct bucketitem* item){
    struct bucketitem* pre=src;
    struct bucketitem* cur=src->next;
    //遍历链表找到cur->data>item->data的位置
    while(cur!=NULL&&cur->data<=item->data){
        pre=cur;
        cur=cur->next;
    }
    //插入节点item，改变item节点next指向cur
    pre->next=item;
    item->next=cur;
}
//打印调试信息
void print_range(int a[],int len,struct bucketitem buckets[]){
    int maxval=a[0],minval=a[0];
    for(int x=0;x<len;x++){
        maxval=a[x]>maxval?a[x]:maxval;
        minval=a[x]<minval?a[x]:minval;
    }
    int s = (maxval-minval)/len+1;
    printf("size:%d\n",s);
    int c = (maxval-minval)/s+1;
    printf("count:%d\n",c);
    for(int i=0;i<c;i++){
        printf("index:%d,[%d,%d)：",i,minval+i*s,minval+(i+1)*s);
        struct bucketitem* cur=buckets[i].next;
        while(cur!=NULL){
            printf("%d ",cur->data);
            cur=cur->next;
        }
        printf("\n");
    }
}

int main()
{
    int len=256;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%256;
    }
    printArray("未排序前",arr,len);
    printf("\n");
    bucket_sort(arr,len);
    printf("\n");
    printArray("在排序后",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

运行结果：

未排序前:18 41 60 63 58 165 92 82 127 111
size:15
count:10
index:0,[18,33)：18
index:1,[33,48)：41
index:2,[48,63)：58 60
index:3,[63,78)：63
index:4,[78,93)：82 92
index:5,[93,108)：
index:6,[108,123)：111
index:7,[123,138)：127
index:8,[138,153)：
index:9,[153,168)：165
桶排序：:18 41 58 60 63 82 92 111 127 165