losophy

桶排序

发表于 更新于

桶排序（Bucket Sort）

桶排序是计数排序的升级版。顾名思义，会使用「桶」，核心思想就是 把要排序的的数据分到几个有序的桶里，每个桶里面的数据在单独进行排序，所有的桶内数据排序完成后，再按照桶的顺序依次取出，组成的序列就是有序的。

为了桶排序的高效，我们需要做到以下两点：
1.在额外空间充足的情况下，尽量增加桶的数量。
2.使用的映射函数能够把输入的 n 个数据均匀的分配到 k 个桶中。

同时，对于桶内元素的排序，选择哪一种排序算法对于性能的影响也至关重要。

如何把百万级别的订单根据金额排序

aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNzk4Nzc4Mi03M2VjMzkwZTZjODU0MTNlLnBuZw

适用场景

比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大而内存有限，无法一次性全部加载到内存中。

比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。
理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int len=sizeof(a)/sizeof(int);

void bucketSort(int a[])
{
    int b[10][len+1]={0};//将b全部置0

    int digits=numOfDigits(a);
    for(int i=1;i<=digits;i++)
    {
        distributeElments(a,b,i);
        collectElments(a,b);
        if(i!=digits)
            zeroBucket(b);
    }
}

int numOfDigits(int a[])
{
    int largest=0;
    for(int i=0;i<len;i++)//获取最大值
    {
        if(a[i]>largest)
            largest=a[i];

        int digits=0;//digits为最大值的位数
        while(largest)
        {
            digits++;
            largest/=10;
        }
    }
    return digits;
}

void distributeElments(int a[],int b[10][len+1],int digits)
{
    int divisor=10;//除数
    for(int i=1;i<digits;i++)
        divisor*=10;
    for(int j=0;j<len;j++)
    {
        int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);
        //numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数
        int num=++b[numOfDigist][0];//用b中第一列的元素来储存每行中元素的个数
        b[numOfDigist][num]=a[j];
    }
}

void collectElments(int a[],int b[10][len+1])
{
    int k=0;
    for(int i=0;i<10;i++)
        (int j=1;j<=b[i][0];j++)
            a[k++]=b[i][j];
}

void zeroBucket(int b[][len+1])
{
    for(int i=0;i<10;i++)
        for(int j=0;j<len+1;j++)
            b[i][j]=0;
}

总结

快排、归并是经济实用型小轿车。而桶排序、计数排序、基数排序则是赛道上的跑车竞速。

相关文章