桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入的数据被分配到了同一个桶中。 3. 示意图 元素分布在桶中： 然后，元素在每个桶中排序：

实例

functionbucketSort(arr,bucketSize){if(arr.length===0){returnarr;}vari;varminValue=arr[0];varmaxValue=arr[0];for(i=1;iif(arr[i]elseif(arr[i]>maxValue){maxValue=arr[i];//输入数据的最大值}}//桶的初始化varDEFAULT_BUCKET_SIZE=5;//设置桶的默认数量为5bucketSize=bucketSize||DEFAULT_BUCKET_SIZE;varbucketCount=Math.floor((maxValue-minValue)/bucketSize)+1;varbuckets=newArray(bucketCount);for(i=0;ifor(i=0;ifor(i=0;ifor(varj=0;jreturnarr;}Java

实例

publicclassBucketSortimplementsIArraySort{privatestaticfinalInsertSortinsertSort=newInsertSort();@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);returnbucketSort(arr,5);}privateint[]bucketSort(int[]arr,intbucketSize)throwsException{if(arr.length==0){returnarr;}intminValue=arr[0];intmaxValue=arr[0];for(intvalue:arr){if(valueelseif(value>maxValue){maxValue=value;}}intbucketCount=(int)Math.floor((maxValue-minValue)/bucketSize)+1;int[][]buckets=newint[bucketCount][0];//利用映射函数将数据分配到各个桶中for(inti=0;ifor(int[]bucket:buckets){if(bucket.lengthcontinue;}//对每个桶进行排序，这里使用了插入排序bucket=insertSort.sort(bucket);for(intvalue:bucket){arr[arrIndex++]=value;}}returnarr;}/***自动扩容，并保存数据**@paramarr*@paramvalue*/privateint[]arrAppend(int[]arr,intvalue){arr=Arrays.copyOf(arr,arr.length+1);arr[arr.length-1]=value;returnarr;}}PHP

实例

functionbucketSort($arr,$bucketSize=5){if(count($arr)===0){return$arr;}$minValue=$arr[0];$maxValue=$arr[0];for($i=1;$i$arr);$i++){if($arr[$i]$minValue){$minValue=$arr[$i];}elseif($arr[$i]>$maxValue){$maxValue=$arr[$i];}}$bucketCount=floor(($maxValue-$minValue)/$bucketSize)+1;$buckets=array();for($i=0;$i$buckets);$i++){$buckets[$i]=[];}for($i=0;$i$arr);$i++){$buckets[floor(($arr[$i]-$minValue)/$bucketSize)][]=$arr[$i];}$arr=array();for($i=0;$i$buckets);$i++){$bucketTmp=$buckets[$i];sort($bucketTmp);for($j=0;$j$bucketTmp);$j++){$arr[]=$bucketTmp[$j];}}return$arr;}C++

实例

#include#include#includeusingnamespacestd;constintBUCKET_NUM=10;structListNode{explicitListNode(inti=0):mData(i),mNext(NULL){}ListNode*mNext;intmData;};ListNode*insert(ListNode*head,intval){ListNodedummyNode;ListNode*newNode=newListNode(val);ListNode*pre,*curr;dummyNode.mNext=head;pre=&dummyNode;curr=head;while(NULL!=curr&&curr->mDatamNext;}newNode->mNext=curr;pre->mNext=newNode;returndummyNode.mNext;}ListNode*Merge(ListNode*head1,ListNode*head2){ListNodedummyNode;ListNode*dummy=&dummyNode;while(NULL!=head1&&NULL!=head2){if(head1->mDatamData){dummy->mNext=head1;head1=head1->mNext;}else{dummy->mNext=head2;head2=head2->mNext;}dummy=dummy->mNext;}if(NULL!=head1)dummy->mNext=head1;if(NULL!=head2)dummy->mNext=head2;returndummyNode.mNext;}voidBucketSort(intn,intarr[]){vectorbuckets(BUCKET_NUM,(ListNode*)(0));for(inti=0;imData;head=head->mNext;}}