桶排序
入门均匀分布时可达 O(n)，理解"分而治之"在排序中的应用。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void bucketSort(int arr[], int n) {
2 int maxVal = *max_element(arr, arr + n);
3 int minVal = *min_element(arr, arr + n);
4 int bucketCount = max(1, n / 2);
5 int bucketSize = (maxVal - minVal + 1) / bucketCount + 1;
6 vector<vector<int>> buckets(bucketCount);
7
8 for (int i = 0; i < n; i++) {
9 int idx = min((arr[i] - minVal) / bucketSize, bucketCount - 1);
10 buckets[idx].push_back(arr[i]);
11 }
12
13 int idx = 0;
14 for (int i = 0; i < bucketCount; i++) {
15 sort(buckets[i].begin(), buckets[i].end());
16 for (int val : buckets[i])
17 arr[idx++] = val;
18 }
19}
复杂度分析
时间 O(n + k)
空间 O(n + k)
最优 O(n + k)
最坏 O(n²)
算法讲解
桶排序将元素按值域范围分到若干个桶中。
每个桶内的元素可以使用其他排序算法（如插入排序）。
最后按桶的顺序依次输出所有元素。
当数据均匀分布时，时间复杂度接近 O(n)。