上次介绍了气泡排序、直接插入排序、希尔排序、选择排序、快速排序、合并排序、堆栈排序、计数排序。 具体细节可以在公众号历史消息中确认。 这次，我们来说明一下桶排序。
一.排序算法系列目录中包括： 气泡排序(Bubble Sort )插入排序(Insertion Sort )外壳程序排序(shell sort )快速排序(Merge Sort )合并排序(heap ) 桶排序)桶排序)或所谓的盒子排序是一种排序算法，原理是将数组分成有限数量的桶。 您可以单独对每个桶进行排序，然后使用其他排序算法，或者使用递归桶排序继续进行排序。 最后，把每个桶里的记录按顺序排序，按顺序记住。 桶排序是鸽巢排序的总结结果。 如果要排序的数组中的数值是均匀分配的，则桶排序使用线性时间((n ) )。 但是，桶排序不是比较排序，不受o(nlogn )下限的影响。
1 .基本思想桶序列的思想接近贯彻分治思想
桶排序假定要排序的组的数量均匀且独立地分布在一个范围内，并将该范围划分为几个子范围(桶)。
然后，根据某个映射函数f将待排序列中的关键字k映射到第I个桶，即桶数组b中的下标I，则关键字k是B[i]的元素。 每个桶B[i]是一组大小为N/M的序列。
然后，将各桶内的数据组织并合并，对各桶B[i]内的所有要素进行比较排序。 可以使用高速列。 然后，依次枚举输出B[0]….B[M]的所有内容，即为有序序列。
补充：映射函数一般由f=array[i]/k； k^2=n； n是全部元素个数
为了使桶的排序更有效率，有必要做以下两点。
在有足够空间可用的情况下，可以将已输入的n个数据平均地分配给k个区段，同时选择什么排序算法对区段中的元素进行排序，可以使用映射函数以尽可能多地增加区段数目
2 .设定定量序列作为空桶以实现逻辑。 找个顺序，把项目一个个放进对应的桶里去。 按非空桶排序。 从非空桶中将项目恢复为原始序列。 3 .视频演示
步骤图说明：阵列array=[ 63，157，189，51，101，47，141，121，157，156，194，117，98，139，67，133，181，132，28
4 .复杂度分析平均时间复杂度： o(nk )最佳时间复杂度： o ) nk )最坏时间复杂度： o ) n^2)空间复杂度： o ) n*k )稳定性：如果稳定桶排序最好，则使用线性时间o ) n )。 桶排序的时间复杂度取决于对桶之间的数据进行排序的时间复杂度。 其他部分的时间复杂度都很明显，时段划分越小，每个时段之间的数据就越少，排序所需的时间也越少。 但是，相应地空间的消耗量会增大。
5 .假设代码实现(c实现)数据分布在[ 0，100 ]之间，用链表表示各数据包内部，在数据进入数据包的同时插入排序。 然后合并各桶的数据。
# include iterator # include iostream # includevectorusingnamespacestd； const int BUCKET_NUM=10； struct listnode { explicit listnode (inti=0) :mData(i ) I，mnext ) {}ListNode* mNext； int mData； (； listnode*insert(listnode*head，int val ) {ListNode dummyNode； listnode * new node=new listnode (val； ListNode *pre，*curr； dummyNode.mNext=head； pre=dummyNode； curr=head； wile (空！=curr curr-mData=val ) {pre=curr； curr=curr-mNext； }newNode-mNext=curr； pre-mNext=newNode； return dummyNode.mNext； }listnode*merge(listnode*head1，ListNode *head2) {ListNode dummyNode； ListNode *dummy=dummyNode； wile (空！=头1空！=head2) if(head1-mdata=head2-mdata ) {dummy-mNext=head1； head1=head1-mNext； }else{dummy-mNext=head2； head2=head2-mNext； }dummy=dummy-mNext； (if )空值！=head1) dummy-mNext=head1； if (空！=head2) dummy-mNext=head2； return dummyNode.mNext； }voidbucketsort(intn，int arr[] ) vectorListNode*buckets ) bucket_num，(listnode* )0) )； for(intI=0； in； I ) {int index=arr[i]/BUCKET_NUM； listnode*head=buckets.at(index )； buckets.at(index )=insert (头)，arr[i]； }listnode*head=buckets.at(0； for(intI=1； iBUCKET_NUM； I ) ) head=merge(head，buckets.at(i ) I )； }for(intI=0； in； I ) {arr[i]=head-mData； head=head-mNext； }三、总结桶排序是计数排序的变种，利用函数的映射关系，是否高效是该映射函数的确定。 通过计数排序，将相邻的m个“小桶”放入一个“大桶”中，将桶分开后，按桶进行排序(一般使用快速排)，合并为最后的结果。
算法的思想与散列中的开放散列法相同，可以适用于碰撞时放在同一个桶中的数据量分布比较均匀的情况，也可以适用于侧重于区间数的情况。
桶排序最重要的建筑桶，如果桶的设计不好，桶排序几乎就不起作用。 通常，上下界有两种取法，第一种取10n或2n的数，容易实现。 另一种是取数列的最大值和最小值分成桶。
上一篇预告：基数排序（Radix Sort）想了解详情，请询问下次分解。
欢迎使用PS:微信公众号： developer1024