排序算法 - 桶排序(Bucket Sort)

by LauCyun Aug 11,2014 20:53:57 10,278 views

桶排序和归并排序有那么点点类似,也使用了归并的思想。大致步骤如下:

  • 设置一个定量的数组当作空桶。
  • Divide - 从待排序数组中取出元素,将元素按照一定的规则塞进对应的桶子去。
  • 对每个非空桶进行排序,通常可在塞元素入桶时进行插入排序。
  • Conquer - 从非空桶把元素再放回原来的数组中。

图1演示了桶排序作用于有10个数的输入数组[4, 47, 60, 93, 29, 3, 52, 75, 22, 86](数据分布在[0,100)之间)上的操作过程:

图1 桶排序过程

 

1 算法实现

伪代码

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

C

 #include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define N 10


void Show(const ElemType *arr, const int n);
void BucketSort(ElemType arr[], int n);


void Show(const ElemType *arr, const int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


void BucketSort(ElemType arr[], int n) {
    /// 找出最大值和最小值
    ElemType maximum = arr[0], minimum = arr[0];
    int i;
    for (i = 1; i < n; ++i) {
        if (maximum < arr[i]) maximum = arr[i];
        if (minimum > arr[i]) minimum = arr[i];
    }

    /// 创建空桶
    ElemType *buckets;
    int buckets_size = maximum - minimum + 1;
    buckets = (ElemType *) malloc(sizeof(ElemType) * buckets_size);
    for (i = 0; i < buckets_size; ++i) {
        buckets[i] = 0;
    }

    /// 把数据放进桶
    for (i = 0; i < n; ++i) {
        buckets[arr[i] - minimum]++;
    }

    /// 从非空桶把元素再放回原来的数组中
    int j;
    for (i = 0, j = 0; i < buckets_size; i++)
        for (; buckets[i] > 0; (buckets[i])--)
            arr[j++] = i + minimum;

}

int main() {
    ElemType array[N] = {4, 47, 60, 93, 29, 3, 52, 75, 22, 86};

    printf("before sorting:\n");
    Show(array, N);

    BucketSort(array, N);

    printf("after sorting:\n");
    Show(array, N);

    return 0;
}  

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def bucketSort(lst):
    """
        桶排序,建立(maximum-minimum)个桶。
    :param lst: 
    :return: 
    """
    maximum = lst[0]
    minimum = lst[0]
    for i in lst:
        if i > maximum:
            maximum = i
        if i < minimum:
            minimum = i

    buckets_size = maximum - minimum + 1
    buckets = [0] * buckets_size
    for j in range(len(lst)):
        buckets[lst[j] - minimum] += 1

    res = []
    for k in range(buckets_size):
        if buckets[k] != 0:
            res += [k + minimum] * buckets[k]
    return res


def insertionSort(alist):
    """
        插入排序
    :param alist: 
    :return: 
    """
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentvalue:
            alist[position] = alist[position - 1]
            position = position - 1

        alist[position] = currentvalue
    return alist


def bucketSort1(lst, maximum):
    """
        桶排序,建立N个桶,N为lst的大小。
    :param lst: 
    :param maximum: 最大值,lst的取值在[0,maximum]之间
    :return: 
    """
    n = len(lst)
    buckets = [[] for i in range(n)]
    for i in range(n):
        index = int(n * lst[i] / maximum)
        buckets[index].append(lst[i])
    res = []
    for i in range(n):
        res.extend(insertionSort(buckets[i]))
    return res


unsortedArray = [4, 47, 60, 93, 29, 3, 52, 75, 22, 86]
print(bucketSort(unsortedArray))
print(bucketSort1(unsortedArray, 100))

 

2 算法过程

如果显示不正常,请戳这里

 

3 复杂度分析

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的\(f(k)\)值的计算,其作用就相当于快排中划分,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

\(N\)个关键字进行桶排序的时间复杂度分为两个部分:

  • 循环计算每个关键字的桶映射函数,这个时间复杂度是\(O(N)\)
  • 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为\(\sum_{i=1}^{n} O(N_{i}*logN_{i})\) 。其中\(N_{i}\)为第\(i\)个桶的数据量。

很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到\(O(N*logN)\)了)。因此,我们需要尽量做到下面两点:

  • 映射函数\(f(k)\)能够将\(N\)个数据平均的分配到\(M\)个桶中,这样每个桶就有\(\frac{N}{M}\)个数据量。
  • 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。 当然,做到这一点很不容易,数据量巨大的情况下,\(f(k)\)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于\(N\)个待排数据,\(M\)个桶,平均每个桶\(\frac{N}{M}\)个数据的桶排序平均时间复杂度为:

\(O(N)+O(M*\frac{N}{M}*log\frac{N}{M})=O(N+N*(logN-logM))=O(N+N*logN-N*logM)\)

\(N=M\)时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到\(O(N)\)

总结:桶排序的平均时间复杂度为线性的\(O(N+K)\),其中\(K=N*(logN-logM)\)。如果相对于同样的\(N\),桶数量\(M\)越大,其效率越高,最好的时间复杂度达到\(O(N)\)。当然桶排序的空间复杂度为\(O(N+M)\),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

 

4 稳定性

桶排序是稳定的。

 

5 海量数据中的应用

应用1

一年的全国高考考生人数为500万,分数使用标准分,最低100,最高900,没有小数,要求对这500万元素的数组进行排序。

分析:对500W数据排序,如果基于比较的先进排序,平均比较次数为\(O(5000000*log5000000)≈1.112\)亿。但是我们发现,这些数据都有特殊的条件:\(100=<score<=900\)。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。

方法:创建801(900-100)个桶。将每个考生的分数丢进\(f(score)=score-100\)的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。而且可以很容易的得到100分有***人,501分有***人。

实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。

应用2:

在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。只写出思路即可(内存限制为2G意思是可以使用2G空间来运行程序,而不考虑本机上其他软件内存占用情况。)

关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=\(\frac{n+1}{2}\) ; 当样本数为偶数时,中位数为\(\frac{n}{2}\)\(\frac{n+1}{2}\)的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

分析:既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。

思想:将整型的每1byte作为一个关键字,也就是说一个整形可以拆成4个keys,而且最高位的keys越大,整数越大。如果高位keys相同,则比较次高位的keys。整个比较过程类似于字符串的字典序。

第一步:把10G整数每2G读入一次内存,然后一次遍历这536,870,912即\(\frac{(1024 * 1024 * 1024) * 2}{4}\)个数据。每个数据用位运算>>取出最高8位(31-24)。这8bits(0-255)最多表示256个桶,那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中,同时在内存中统计每个桶内数据的数量,自然这个数量只需要256个整形空间即可。

代价:

  • 10G数据依次读入内存的IO代价(这个是无法避免的,CPU不能直接在磁盘上运算)。
  • 在内存中遍历536,870,912个数据,这是一个\(O(n)\)的线性时间复杂度。
  • 把256个桶写回到256个磁盘文件空间中,这个代价是额外的,也就是多付出一倍的10G数据转移的时间。

第二步:根据内存中256个桶内的数量NUM[256],计算中位数在第几个桶中。

很显然,2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加,发现少于1,342,177,280,把第128个桶数据量加上,大于1,342,177,280。说明中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(若数据大致是均匀分布的,每个文件的大小估计在10G/256=40M左右,当然也不一定,但是超过2G的可能性很小)。

注意,变态的情况下,这个需要读入的第128号文件仍然大于2G,那么整个读入仍然可以按照第一步分批来进行读取。

代价:

  • 循环计算255个桶中的数据量累加,需要\(O(M)\))的代价,其中m<255。
  • 读入一个大概80M左右文件大小的IO代价。

第三步:继续以内存中的某个桶内整数的次高8bit(他们的最高8bit是一样的)进行桶排序(23-16)。过程和第一步相同,也是256个桶。

第四步:一直下去,直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

整个过程的时间复杂度在\(O(n)\)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上,即10G数据分255个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

 

6 参考文档

(全文完)

Tags