这篇文章主要介绍了C语言实现桶排序的方法,简单描述了桶排序的概念、原理并结合实例形式分析了C语言实现桶排序算法的具体操作技巧,需要的朋友可以参考下
本文实例讲述了C语言实现桶排序的方法。分享给大家供大家参考，具体如下：
一、定义
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 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]是一指针数组，指向桶（链表）。
二、性能
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
快排的时间复杂度为n*log2(n)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序是稳定的
三、实现
/*============================== 8 name:bucket sort -------------------------------- time complexity: average O(n+nlogn-nlogm) -------------------------------- space complexity: O(n) -------------------------------- stability: unstable ==============================*/ //suppose: 0<data[i]<100 //we should design the project function based on the data distribution void bucket_sort(std::vector &a) { std::vector<std::vector> bucket; bucket.resize(10); std::vector::iterator it=a.begin(); while(it!=a.end()) { int idx=*it/10; bucket[idx].push_back(*it); it++; } std::vector<std::vector>::iterator it1=bucket.begin(); while(it1!=bucket.end()) { simple_sort(*it1); it1++; } it=a.begin(); it1=bucket.begin(); while(it!=a.end() && it1!=bucket.end()) { std::vector::iterator tmp_it=(*it1).begin<b style="color:transparent">来源gao@dai!ma.com搞$代^码网</b>(); while(tmp_it!=(*it1).end()) { *it=*tmp_it; tmp_it++; it++; } it1++; } }
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.gaodaima.com/aideddesign/paixu_ys
希望本文所述对大家C语言程序设计有所帮助。
以上就是C语言实现桶排序的方法示例的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C语言实现桶排序的方法示例
转载请注明原文链接：C语言实现桶排序的方法示例
