简述
桶排序需要创建若干个桶来协助排序。
所谓桶，每个桶
bucket代表一个区间范围，里面可以承载一个或多个元素。
复杂度
| 名称 | 最好 | 平均 | 最差 | 空间 | 稳定性 |
| 桶排序 | n+k | n | nlog(n) | n | 是 |
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
void BucketSort(double* pData, int size) { if (nullptr == pData || size <= 1) return; double minData = pData[0]; double maxData = pData[0]; for (int idx = 0; idx < size; ++idx) { if (pData[idx] < minData) minData = pData[idx]; if (pData[idx] > maxData) maxData = pData[idx]; } double d = maxData - minData; // 创建桶 int bucketCount = (maxData - minData) / size + 1; // 桶数计算公式 std::vector<std::vector<double>> buckets(bucketCount); // 向桶中插入数据 for (int idx = 0; idx < size; ++idx) { // 桶下标计算公式 int bucketIdx = static_cast<int>((pData[idx] - minData)*(bucketCount - 1) / d); buckets[bucketIdx].push_back(pData[idx]); } // 各个桶就行排序 for (int idx = 0; idx < bucketCount; ++idx) { if (buckets[idx].empty()) continue; std::sort(buckets[idx].begin(), buckets[idx].end()); } // 将桶中数据写回原数组 for (int idx = 0, curIdx = 0; idx < bucketCount; ++idx) { auto& curBucket = buckets[idx]; if (curBucket.empty()) continue; for (auto& curData : curBucket) pData[curIdx++] = curData; } } |
算法导论
桶排序思想，假设对数组A[p...r]排序，首先将这些元素进行hash运算，根据其hash值放入桶的对应区间中；然后对每一个区间中的元素进行排序；最后合并桶中各区间排序好的结果得到排序的数据：
- hash算法必须满足：若 a<b ，则hash(a)<hash(b)
- 要求 hash的结果尽量好，使得各数据平均分布在各区间内
- 期望时间复杂度 O(n)
- 非原地排序
- begin : 待排序序列的起始迭代器（也可以是指向数组中某元素的指针）
- end: 待排序序列的终止迭代器（也可以是指向数组中某元素的指针）
- min_val:待排序序列元素的下界（不一定是最紧下界）
- max_val:待排序序列元素的上界（不一定是最紧上界）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
template<typename Iterator> void bucket_sort(const Iterator begin,const Iterator end,const typename std::iterator_traits<Iterator>::value_type& min_val, const typename std::iterator_traits<Iterator>::value_type& max_val) { assert(min_val<max_val); //确保最小值小于最大值 typedef typename std::iterator_traits<Iterator>::value_type T; // 迭代器指向对象的值类型 std::size_t real_bucket_num=10; //划分10个区间 std::vector<T> buckets[real_bucket_num]; Iterator iter=begin; while(iter!=end) { auto value=*iter; auto index=(value-min_val)*real_bucket_num/(max_val-min_val); // 这里采取最简单的hash：线性分布 if(index<real_bucket_num) buckets[index].push_back(value); //放元素到桶中 else buckets[real_bucket_num-1].push_back(value); //最后一个区间放超大数 iter++; } std::size_t inserted_total=0; for(std::size_t i=0;i<real_bucket_num;i++) { quick_sort<typename std::vector<T>::iterator>(buckets[i].begin(),buckets[i].end());//对某个区间排序 std::copy(buckets[i].begin(),buckets[i].end(),begin+inserted_total);//排序后放回原容器（因此是非原地） inserted_total+=buckets[i].size(); } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 数据结构_最小优先级队列10/10
- ♥ BFS和DFS06/29
- ♥ 查找_顺序查找05/09
- ♥ 大话数据结构_算法相关&&AVL&&B树相关02/20
- ♥ 动态规划相关06/29
- ♥ 排序_冒泡排序05/08