基础十大排序(7) ———桶排序(C语言版) ) ) ) )。
桶排序（Bucket sort）
桶排序(Bucket sort )和所谓的箱子排序是一种排序算法，原理是将数组分成有限数量的桶。 对每个桶分别排序。 您可以使用其他排序算法，也可以继续使用桶排序递归排序。 桶排序是鸽巢排序的总结结果。 如果要排序的数组中的数值是均匀分配的，则桶排序使用线性时间((n ) )。 但是，桶排序不是比较排序，不受o(nlogn )下限的影响。
什么是桶排序
以下来自百度百科：
输入是均匀分布在由随机进程生成的[ 0，1 ]区间的实数。 将区间[ 0，1 ]分为大小相等的n个子区间(桶)，桶1/n )的大小为，
1/n )、[1/n，2/n、[2/n，3/n、[k/n，(k 1 )/n ] ]
、…向这些桶分配n个输入元素，对桶内的元素进行排序，依次连接桶，输入0 A[1…n]
1辅助数组B[0…n-1]是指向存储桶(链表)的指针数组。
算法描述
桶排序利用函数的映射关系，减少了大部分的比较工作。 实际上，桶排序的f(k )值的计算相当于高速排序中的分割，将大量的数据分割为基本上有序的块)桶)。 然后，只需将桶里少量的数据进行高度比较和排序即可。 3358 www.Sina.com/# include stdio.hint main ((inta [ 100 ]，t，max=sizeof(a ) a )/sizeof ) int )； for(intI=0； imax； I ) a(I )=0； for(intj=0； j5； j ) Scanf('%d '，t )； a[t]； }for(intk=0； kmax； k ) for(inty=0； ya[k]； y ) printf('%d '，k )； 返回0； } 代码实现
动态描述
桶排序的平均时间复杂度为线性的选择排序复杂度分析，其中O(N+C)。 对于相同的C=N*(logN-logM)，桶数3358www.Sina.com/越大，效率越高，最佳的时间复杂度为N。 当然，桶排序的空间复杂度为M，在输入数据非常庞大，桶的数量也非常多的情况下，空间成本无疑是昂贵的。 此外，桶顺序为O(N)
O(N+M)
文章如有错误，欢迎指正。 在下一座完美的山上，各位请原谅。