桶排序¶
前置知识¶
插入排序
目标¶
算法思想，代码模板
桶排，非比较排序，稳定¶
桶排序（Bucket sort）的原理是将数组分到有限数量的桶里。
每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
如果桶内的排序采用插入排序，那么就是稳定的。
算法步骤：
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。
由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。
平均时间复杂度，\(O(n + \frac{n^2}{k}+k)\)，\(k\) 是桶的个数。当 \(k\approx n\) 时，\(O(n)\)
最坏时间复杂度，\(O(n^2)\)
最坏空间复杂度，\(O(n * k)\)
讨论¶
每个桶内再用其他的排序算法进行排序（比如快排），这样子时间复杂度不还是 \(O(nlogn)\)吗？
如果要排序的数据有 \(n\) 个，我们把它们分在 \(m\) 个桶中，这样每个桶里的数据就是 \(k = n / m\)。
每个桶内排序的时间复杂度就为\(O(k*logk)\)。
\(m\) 个桶就是 \(m * O(k * logk)\) = \(m * O((n / m)*log(n / m))\) = \(O(n * log(n / m))\)。
当桶的个数 \(m\) 接近数据个数 \(n\) 时，\(log(n/m)\) 就是一个较小的常数，所以时间复杂度接近 \(O(n)\)。
既然桶排序时间复杂度为线性，是不是就能替代例如快排归并这种时间复杂度为 \(O(nlogn)\)的排序算法呢？
答案是否定的，桶排序的应用场景十分严苛。
首先，数据应该分布比较均匀。讲一种较坏的情况，如果数据全部都被分到一个桶里，那么桶排序的时间复杂度是不是就退化到 \(O(nlogn)\)了呢？
其次，要排序的数据应该很容易分成 \(m\) 个桶，每个桶也应该有大小顺序。
桶排序适合用在外部排序中，就是数据存储在外部磁盘上，由于服务器内存有限无法一次性加载到内存中。
比如现在有 \(10G\) 订单数据存在外部磁盘的一个文件中，我们想将这 \(10G\) 的订单数据按照从小到大进行排序，但是由于服务器内存有限只有几百 \(M\)，无法一次性加载内存，这时候就可以利用桶排序进行解决了。
思路:
可以先找出这批订单的最大值和最小值，比如扫描一遍文件，最大值是 \(10\) 万，最小值是 \(1\) 元，那么我们可以将这 \(10G\) 的订单分别划分到 \(100\) 个桶中，比如：\(1\) 元到 \(1000\) 元的放在第一个桶内，\(1001\) 到 \(2000\) 元的放到第二个桶内，以此类推。每个桶我们最终都会生成一个文件，这个小文件中存放的都是之前划分的那些订单数据，我们进行一个编号，比如 \((00,01,02,...99)\).
理想情况：
理想情况下，这 \(10\) 万的订单数据均匀分布到 \(100\) 个桶中，每个桶都存放 \(1000\) 个订单，每个桶即每个子文件大约是存储 \(100M\) 的数据，那么这 \(100\) 个子文件依次加载到内存中进行快速排序，排序完成后。我们依次读取每个子文件的数据并写入到一个大文件中，这样以来这 \(10G\) 的数据就排序完成了。
实际情况：
实际情况是这 \(10G\) 订单数据不可能是均匀分布的，一般人买东西肯定是金额低的多一些，金额高的就很少了，所以每个桶内不可能是很均匀的，这种情况的处理办法就是继续划分这个数据量大的桶为几个子桶，一直到每个桶的数据可以被一次性读入内存为止。
代码模板¶
#include <bits/stdc++.h>
using namespace std;
int a[110], n;
int w; // 值域
void insertion_sort(vector<int> &A) {
int len = A.size();
for (int i = 1; i < len; i++) {
int j = i - 1, cur = A[i];
while (j >= 0 && A[j] > cur) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = cur;
}
}
void bucket_sort(int a[]) {
int sz = w / n + 1;
vector<int> bucket[110];
for (int i = 0; i < n; i++) {
bucket[a[i] / sz].push_back(a[i]);
}
int idx = 0;
for (int i = 0; i < n; i++) {
insertion_sort(bucket[i]);
for (auto x : bucket[i])
a[idx++] = x;
}
}
int main(){
cin >> n >> w;
for (int i = 0; i < n; i++) cin >> a[i];
bucket_sort(a);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
puts("");
return 0;
}
参考¶
https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
https://oi-wiki.org/basic/bucket-sort/