桶排序(bucket sort)是一种时间复杂度为线性时间(O(n))的排序。

其原理如下：（参考算法导论第8章）

桶排序将[0,1)区间划分为n个大小相同的子区间，每个子区间称之为桶。桶与桶之间是有序的。

对于n个输入的数，分别落入不同每一个桶中。

落入同一个桶中的元素在结点接入的过程中要查找到其对应的位置。

最终排好序的输出是由每个桶里的链表依次连接而成的。

 

用简单的话来打个比方:

假设n为10

则桶的编号为B[0]、B[1]、...B[9]

对于arr[m]中输入的元素：

0.01落入B[0]中，0.63落入B[6]中，0.88落入B[8]中……

而落入同一个桶中的元素0.37、0.38、0.31在桶中呈如下排列(链表有序）

B[3]->(0.31)->(0.37)->(0.38)

最后再按照B[0]、B[1]、...B[9]的顺序 可以抽象地理解为把链表像烤章鱼小丸子似的按顺序串起来

放回原来的数组arr[m]中

其算法过程可以分为以下四个部分：

1、建立桶、清空桶

2、遍历输入集、放入桶

3、桶内查找正确位置，接入链表

4、桶的排放顺序将链表里的元素放回输入集中

详细实现与注解见详细代码：

1 #include
     
       2 using namespace std; 3 struct Node//声明链表结点 4 { 5     double value; 6     Node *next; 7 }; 8 void bucketsort(double *arr,int length) 9 {10     Node key[10];11     int number=0;12     Node *p,*q;13     int index=0;14     /*1、建立桶、清空桶*/15     for(int i=0; i<10; i++)16     {17         key[i].value=0;18         key[i].next=NULL;19     }20     for(int i=0; i
      
       value=arr[i];25         ins->next=NULL;26         number=arr[i]*10;//计算该元素在这排桶中对应的下标27         /*3、桶内查找正确位置，接入链表*/28         if(key[number].next==NULL)//如果当前桶为空，则直接接入元素29         {30             key[number].next=ins;31         }32         else//否则顺着链表向下查找当前arr[i]元素的插入位置。33         {34             p=&key[number];35             q=key[number].next;36             while((q!=NULL)&&(q->value<=arr[i]))37             {38                 q=q->next;39                 p=p->next;40             }41             ins->next=q;42             p->next=ins;43         }44     }45     /*4、桶的排放顺序将链表里的元素放回输入集*/46     for(int i=0; i<10; i++)47     {48         p=key[i].next;49         if(p==NULL) continue;50         while(p!=NULL)//把桶里的元素放回数组51         {52             arr[index++]=p->value;53             p=p->next;54         }55 56     }57 }58 59 int main()60 {61     double arr[]= {
   0.56,0.17,0.23,0.94,0.55,0.67,0.81,0.94,0.13,0.48};62     bucketsort(arr,10);63     for(int i=0; i<10; i++)64     {65         cout<
       
        <<" ";66     }67     cout<