vlambda博客
学习文章列表

【数据结构与算法】桶排序

桶排序(Bucket Sort)

桶排序也叫箱排序。工作的原理是将数组元素映射到有限数量个桶里,每个桶各自进行桶内排序,最后将多个桶的排序结果合并。

桶排序的实现代码如下:

def bucketSort(arr, bucketSize): if len(arr) < 2: return
# 数组最小值 minValue = arr[0] # 数组最大值 maxValue = arr[1] for i in range(len(arr)): if arr[i] < minValue: minValue = arr[i] elif arr[i] > maxValue: maxValue = arr[i]
# 桶数量 bucketCount = (maxValue - minValue) // bucketSize + 1 # [bucketCount, bucketSize]维度的数组 buckets = [[0 for i in range(bucketCount)] for j in range(bucketSize)] indexArr = [0 for i in range(bucketCount)]
# 将数组中的值分配到各个桶里 for i in range(len(arr)): # 分配到哪个桶 bucketIndex = (arr[i] - minValue) // bucketSize # 如果桶里已经装满了,扩容 if indexArr[bucketIndex] == len(buckets[bucketIndex]): ensureCapacity(buckets, bucketIndex) # 把元素加到桶里,并记录桶中元素的个数 buckets[bucketIndex][indexArr[bucketIndex]] = arr[i] indexArr[bucketIndex] += 1
# 对每个桶进行排序,这里使用了快速排序 k = 0 for i in range(len(buckets)): if indexArr[i] == 0: continue quickSortC(buckets[i], 0, indexArr[i] - 1) for j in range(indexArr[i]): arr[k] = buckets[i][j] k += 1
# 扩容函数def ensureCapacity(buckets, bucketIndex): tempArr = buckets[bucketIndex] newArr = [0 for i in range(len(tempArr)*2)] newArr[:len(tempArr)] = tempArr[:] buckets[bucketIndex] = newArr
# 快速排序递归函数def quickSortC(arr, p, r): if p >= r: return
q = partition(arr, p, r) quickSortC(arr, p, q - 1) quickSortC(arr, q + 1, r)
# 分区函数# 返回分区点位置def partition(arr, p, r): pivot = arr[r] i = p for j in range(p,r): if arr[j] <= pivot: swap(arr, i, j) i += 1
swap(arr, i, r) return i
# 交换def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]

桶排序相关分析

1.时间复杂度和稳定性

如果要排序的数据有 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)。

桶排序不是比较排序,不受到O(nlogn)下限的影响,它是鸽巢排序的一种归纳结果,当所要排序的数组值分散均匀的时候,桶排序拥有线性的时间复杂度。

最差时间复杂度 —— O(nlogn)或O(n^2),只有一个桶,取决于桶内排序方式

最优时间复杂度 —— O(n),每个元素占一个桶

平均时间复杂度 —— O(n),保证各个桶内元素个数均匀即可

稳定性 —— 稳定

2.特性

桶排序对要排序数据的要求是非常苛刻的。

首先,要排序的数据需要很容易就能划分成 m 个桶,并且,桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。

其次,数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后,有些桶里的数据非常多,有些非常少,很不平均,那桶内数据排序的时间复杂度就不是常量级了。在极端情况下,如果数据都被划分到一个桶里,那就退化为 O(nlogn) 的排序算法了。

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

3.应用

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

我们可以先扫描一遍文件,看订单金额所处的数据范围。假设经过扫描之后我们得到,订单金额最小是 1 元,最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里,第一个桶我们存储金额在 1 元到 1000 元之内的订单,第二桶存储金额在 1001 元到 2000 元之内的订单,以此类推。每一个桶对应一个文件,并且按照金额范围的大小顺序编号命名(00,01,02…99)。

理想的情况下,如果订单金额在 1 到 10 万之间均匀分布,那订单会被均匀划分到 100 个文件中,每个小文件中存储大约 100MB 的订单数据,我们就可以将这 100 个小文件依次放到内存中,用快排来排序。等所有文件都排好序之后,我们只需要按照文件编号,从小到大依次读取每个小文件中的订单数据,并将其写入到一个文件中,那这个文件中存储的就是按照金额从小到大排序的订单数据了。

不过,订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ,所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多,划分之后对应的文件就会很大,没法一次性读入内存。这又该怎么办呢?

针对这些划分之后还是比较大的文件,我们可以继续划分,比如,订单金额在 1 元到 1000 元之间的比较多,我们就将这个区间继续划分为 10 个小区间,1 元到 100 元,101 元到 200 元,201 元到 300 元…901 元到 1000 元。如果划分之后,101 元到 200 元之间的订单还是太多,无法一次性读入内存,那就继续再划分,直到所有的文件都能读入内存为止。

如何根据年龄给 100 万用户排序?

实际上,根据年龄给 100 万用户排序,就类似按照成绩给 50 万考生排序。我们假设年龄的范围最小 1 岁,最大不超过 120 岁。我们可以遍历这 100 万用户,根据年龄将其划分到这 120 个桶里,然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

参考资料

极客时间专栏《数据结构与算法之美》