WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
算法基础简介
枚举
模拟
递归 & 分治
贪心
排序简介
选择排序
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序
堆排序
桶排序
希尔排序
锦标赛排序
排序相关 STL
排序应用
前缀和 & 差分
二分
倍增
22 objects
本站非官方,所收集资源均来源于网络。
桶排序 - 算法基础
本页面将简要介绍桶排序。 ## 简介 桶排序(英文:Bucket sort)是排序算法的一种,适用于待排序数据值域较大但分布比较均匀的情况。 ## 工作原理 桶排序按下列步骤进行: 1. 设置一个定量的数组当作空桶; 2. 遍历序列,并将元素一个个放到对应的桶中; 3. 对每个不是空的桶进行排序; 4. 从不是空的桶里把元素再放回原来的序列中。 ## 性质 ### 稳定性 如果使用稳定的内层排序,并且将元素插入桶中时不改变元素间的相对顺序,那么桶排序就是一种稳定的排序算法。 由于每块元素不多,一般使用插入排序。此时桶排序是一种稳定的排序算法。 ### 时间复杂度 桶排序的平均时间复杂度为 $O(n + n^2/k + k)$ (将值域平均分成 $n$ 块 + 排序 + 重新合并元素),当 $k\approx n$ 时为 $O(n)$ 。[^ref1] 桶排序的最坏时间复杂度为 $O(n^2)$ 。 ## 算法实现 ### C++ ```cpp const int N = 100010; int n, w, a[N]; vector
bucket[N]; void insertion_sort(vector
& A) { for (int i = 1; i < A.size(); ++i) { int key = A[i]; int j = i - 1; while (j >= 0 && A[j] > key) { A[j + 1] = A[j]; --j; } A[j + 1] = key; } } void bucket_sort() { int bucket_size = w / n + 1; for (int i = 0; i < n; ++i) { bucket[i].clear(); } for (int i = 1; i <= n; ++i) { bucket[a[i] / bucket_size].push_back(a[i]); } int p = 0; for (int i = 0; i < n; ++i) { insertion_sort(bucket[i]); for (int j = 0; j < bucket[i].size(); ++j) { a[++p] = bucket[i][j]; } } } ``` ## 参考资料与注释 [^ref1]: [(英文)Bucket sort - Wikipedia](https://en.wikipedia.org/wiki/Bucket_sort#Average-case_analysis)