桶排序

桶排序C语言：

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
typedef struct LNode{
        int data;
        struct LNode *next;
   } LinkList;
void BucketSort(int arr[],int max,int min,int arr_length,int bucketSize);
int main()
{
   int arr[]={1,10,95,36,57,34,85,56,30,55,81,27,100,-1,888,-90,53,123};
   int arr_length=sizeof(arr)/sizeof(int);
   //打印原数组
   printf("原数组为：");
   for(int i=0;i<arr_length;i++){
    printf("%d ",arr[i]);
   }
   printf("\n");
   int min=arr[0],max=arr[0];
   for(int i=0;i<arr_length;i++){
        if(arr[i]<min){
            min=arr[i];
        }
        if(arr[i]>max){
            max=arr[i];
        }
   }
   printf("数组arr的最小值%d,最大值%d",min,max);
   printf("\n");
   //进行桶排序
   printf("桶排序的结果为：");
   BucketSort(arr,max,min,arr_length,arr_length);

}


void BucketSort(int arr[],int max,int min,int arr_length,int bucketSize){
    LinkList **bucket=(LinkList**)malloc(bucketSize*sizeof(LinkList)); //开辟二维空间
    for(int i=0;i<bucketSize;i++){  //每个一维都是单链表
        bucket[i]=(LinkList*)malloc(sizeof(LinkList));
        bucket[i]->data=0;
        bucket[i]->next=NULL;
    }
    for(int j=0;j<arr_length;j++){
        LinkList *node=(LinkList*)malloc(sizeof(LinkList));//创建一个节点的链表，数据域为数组元素
        node->data=arr[j];
        node->next=NULL;
        float temp=(arr[j]-min)/(float)(max-min);   //将数组元素化为0~1中的数，用temp保存起来，下面将判断此数据应放在哪个桶中
        int index=-1;
        for(int i=0;i<bucketSize;i++){
            if(1.0*i/bucketSize<=temp&&1.0*(i+1)/bucketSize>=temp)
                index=i; //桶的索引为index
        }
        LinkList *p=bucket[index];   //定义指针p,它指向此链表的头节点
        if(p->data==0){  //p->data保存的是此链表的节点数（除头节点）
            bucket[index]->next=node;
            (bucket[index]->data)++;
        }
        else{
            while(p->next!=NULL&&p->next->data<node->data){//除头节点外，若还有其他节点，则p一步步地指向最后一个节点数据域比node节点数据域小的节点
                p=p->next;
            }
            node->next=p->next;    //将node节点插入到p所指向的节点的后面
            p->next=node;
            (bucket[index]->data)++;
        }
    }
    LinkList *k=NULL;
    for(int i=0;i<bucketSize;i++){//从大到小输入桶中的数据
        for(k=bucket[i]->next;k!=NULL;k=k->next)
            printf("%d ",k->data);
    }
    printf("\n");
}