桶排序

桶排序

桶排序的基本思想是假设数据在[min,max]之间均匀分布，其中min、max分别指数据中的最小值和最大值。那么将区间[min,max]等分成n份，这n个区间便称为n个桶。将数据加入对应的桶中，然后每个桶内单独排序。由于桶之间有大小关系，因此可以从大到小(或从小到大)将桶中元素放入到数组中。

桶数: (max - min) / array.length的结果为数组大小的倍数（最大倍数），以倍数作为桶数

【注意1】当序列大小vec.size()比较小，而元素值很大且分散(max - min比较大)，会造成很多“空桶”, 增加系统开销，比如(0, 13, 19892)——> 很多“空桶” 【注意2】：当待排序序列元素个数很多(vec.size()很大), 但是每个元素却又很小时, 只有一个桶, 这种情况比较耗时

void BucketSort(vector& vec){ int max = vec[0]; int min = vec[0]; // 确定元素的最值 for (auto it : vec) { if (it > max) max = it; if (it < min) min = it; } // 桶数: (max - min) / array.length的结果为数组大小的倍数（最大倍数），以倍数作为桶数 // 【注意1】当序列大小vec.size()比较小，而元素值很大且分散(max - min比较大)，会造成很多“空桶”, 增加系统开销 // 比如(0, 13, 19892)——> 很多“空桶” // 【注意2】：当待排序序列元素个数很多(vec.size()很大), 但是每个元素却又很小时, 只有一个桶, 这种情况比较耗时 int bucketNum = (max - min) / vec.size() + 1; // 初始化桶, 可以用数组实现, 也可以用vector实现, 这里选取vector实现, 原因下述 // int** buckets = new int*[bucketNum]; // 数组实现桶，需要二维数组 vector > vecBucket; // vector容器实现桶，类似二维数组 // 桶初始化 for (size_t i = 0; i < bucketNum; i++) { vector vecTmp; vecBucket.push_back(vecTmp); } // 用数组实现桶初始化 // for (size_t i = 0; i < bucketNum; i++) // { // buckets[i] = new int[vec.size()]; // 每个桶最多存放vec.size()个元素 // } // 将待排序元素挨个放入对应桶中 for (size_t i = 0; i < vec.size(); i++) { // 和上面【注意】结合看，如果只有1个桶, 要分开处理 if (bucketNum == 1) { vecBucket[0].push_back(vec[i]); } else { int bucketIndex = (vec[i] - min) / bucketNum; // 确定存放在哪个桶 bucketIndex = bucketIndex >= bucketNum ? bucketNum - 1 : bucketIndex; vecBucket[bucketIndex].push_back(vec[i]); // 这是用vector实现桶的好处, 直接“接”在后面自动扩容即可, 数组实现还需代码处理 } } vec.clear(); // 遍历“桶组合”, 给每个桶中元素排序 // 每个桶元素有序了, 则整个“桶组合”从“编号小”的桶遍历到“编号大”的桶，则为整体有序序列 for (vector >::iterator iter = vecBucket.begin(); iter != vecBucket.end(); iter++) { vector vecTmp = *iter; // *iter也是一个vector, 内部存放了该桶内元素 if (vecTmp.size() <= 0) { continue; } // 对每个桶进行排序, 这里借用选择排序 // 当n较小时，对稳定性不作要求时宜用选择排序 //SelectSort(vecTmp); sort(vecTmp.begin(),vecTmp.end()); for (auto it : vecTmp) { // 每个桶内元素有序后, 重新给vec赋值, 此时vec有序。 vec.push_back(it); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。