数据结构应用之桶排序

问： 有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