【数据结构与算法】桶排序
桶排序(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 万用户数据。
参考资料
极客时间专栏《数据结构与算法之美》