桶排序(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<iostream> 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<length; i++) 21 { 22 /*2、遍历输入集、放入桶*/ 23 Node *ins=new Node(); 24 ins->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<<arr[i]<<" "; 66 } 67 cout<<endl; 68 return 0; 69 }