问： 有10G的订单数据，希望订单金额(假设都是正整数)进行排序，但我们内存有限，只有几百MB,如何进行排序？
答： 因内存有限，需要排序的数据量巨大，所以，此时需要外部排序，外部排序采用的是一种分治思想，外部排序最常用的是多路归并排序，即将大数据切成多份一次可以载入内存的小数据，对小数据进行内存排序，然后再对排序好的多个小数据进行归并排序。然而，本节将介绍它的一种变体--桶排序，它的主要是将待排序的数据分到若干个桶中，然后对每个桶内数据进行排序，最后取出桶内的数据组成有序列表。
PS：上代码：
桶内数据结构
struct barrel{
int node[10]; //桶内最多支持10个数据
int count; //节点数量
};
"桶里"排名 -- 桶内排序采用快速排序
int partition(int a[], int left, int right)
{
int key = a[left];
while(left < right)
{
while((left < right) && a[right] >= key)
{
right--;
}
if(left < right)
{
a[left] = a[right];
}
while((left < right) && a[left] <= key)
{
left++;
}
if(left < right)
{
a[right] = a[left];
}
}
a[left] = key;
return left;
}
void quick_sort(int a[], int left, int right)
{
int q = 0;
// 终止条件
if(left >= right)
{
return;
}
q = partition(a, left, right);
quick_sort(a, left, (q-1));
quick_sort(a, (q+1), right);
return ;
}
桶排序，数据"分桶"
void bucket_sort(int data[], int size)
{
int max, min, num, pos;
int i, j, k;
struct barrel *pBarrel;
max = min = data[0];
for(i = 1; i < size; ++i)
{
max = data[i] > max ? data[i] : max;
min = data[i] < min ? data[i] : min;
}
num = (max - min + 1) / 10 + 1; // 通过最大值最小值计算需要多少个桶，此处每个桶最多能存10个数据
pBarrel = (struct barrel *)malloc(sizeof(struct barrel) * num);
memset(pBarrel, 0, sizeof(struct barrel) * num);
for(i = 0; i < size; ++i)
{
k = (data[i] - min + 1) / 10; // 计算该数据属于第几个桶
(pBarrel + k)->node[(pBarrel + k)->count] = data[i]; // 将该数据存入第k个桶中的第count的数据
(pBarrel + k)->count++; // 该桶内数据数据加1
}
// 桶内数据排序，快速排序
pos = 0;
for(i = 0; i < num; ++i)
{
if((pBarrel + i)->count != 0)
{
quick_sort((pBarrel + i)->node, 0, (pBarrel + i)->count-1);
for(j = 0; j < (pBarrel + i)->count; ++j)
{
data[pos++] = (pBarrel+i)->node[j];
}
}
}
free(pBarrel);
}
模拟数据
void bucket_sort_test()
{
int a[] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 91};
int size = sizeof(a) / sizeof(int);
printf("\r\n bucket sort test ...\n");
bucket_sort(a, size);
dump(a, size);
}
int main()
{
// 桶排序
bucket_sort_test();
return 0;
}
时间复杂度分析：
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有$ k=n/m $个元素。每个桶内部使用快速排序，时间复杂度为 \(O(k * logk)\)。m 个桶排序的时间复杂度就是 \(O(m * k * logk)\)，因为 k=n/m，所以整个桶排序的时间复杂度就是$ O(n*log(n/m))$。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 \(O(n)\)。
模板实现：
#ifndef TEMPLATE_SORT_BUCKET_HPP_
#define TEMPLATE_SORT_BUCKET_HPP_
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
template <size_t BucketSize,
typename IterT,
typename T = typename std::iterator_traits<IterT>::value_type,
typename Compare = std::less<T>>
void bucket_sort(IterT first, IterT last, Compare comp = Compare())
{
const T min = *std::min_element(first, last), max = *std::max_element(first, last);
const T range = max - min + 1;
const size_t bucket_num = range / BucketSize + 1;
std::vector<std::vector<T>> buckets(bucket_num);
// 为桶内数据预留空间
for(auto b : buckets)
{
b.reserve(2 * BucketSize);
}
for(IterT i = first; i != last; ++i)
{
size_t idx = (*i - min + 1) / BucketSize;
buckets[idx].emplace_back(*i);
}
IterT dest = first;
for(auto b: buckets)
{
std::sort(b.begin(), b.end(), comp);
std::copy(b.begin(), b.end(), dest);
dest += b.size();
}
return;
}
#endif
调用
template <size_t BucketSize,
typename Container,
typename T = typename Container::value_type,
typename Compare = std::less<T>>
void test_bucket_sort(Container cont, Compare comp = Compare()) {
bucket_sort<BucketSize>(cont.begin(), cont.end(), comp);
std::transform(cont.begin(), cont.end(), std::ostream_iterator<T>(std::cout, " "),
[](T i){ return i; });
std::cout << std::endl;
}
int main() {
std::vector<int> test{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
test_bucket_sort<2>(test); // 1 1 2 3 3 4 5 5 5 6 7 8 9 9 9
test_bucket_sort<3>(test); // 1 1 2 3 3 4 5 5 5 6 7 8 9 9 9
test_bucket_sort<4>(test); // 1 1 2 3 3 4 5 5 5 6 7 8 9 9 9
test_bucket_sort<5>(test); // 1 1 2 3 3 4 5 5 5 6 7 8 9 9 9
test_bucket_sort<6>(test); // 1 1 2 3 3 4 5 5 5 6 7 8 9 9 9
return 0;
}
参考：https://time.geekbang.org/column/article/42038?cid=100017301