排序算法——桶排序

发表于 更新于 分类于 ， ， ，

介绍

桶排序(Bucket sort)是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

如果桶的大小划分得足够小，到达每个元素之间的最小差值，则可以保证每一个桶里面所有的数据都是一样的，入桶后的数据也就不需要再次进行排序，这种情况也就是桶排序时间复杂度最优的情况即\(O(n)\).一般情况下桶排序的时间复杂度为\(O(n+nlog(\frac{n}{m}))\)，其中n为元素个数，m为桶个数。

实现

桶排序的大致步骤如下：

  • 确定桶的大小与个数，一般根据要排序的元素的值域区间取定。
  • 设计一种方式使元素能映射至对应值域的桶的索引。
  • 遍历所有元素，将它们入桶。
  • 每个桶内元素排序。
  • 从桶内依次提取各元素重新排列。

以下是一个简单的桶排序过程。显而易见，所有元素的值都在50~59之间，因此可以使用\(a-50\)这样一个映射关系将所有元素映射至10个桶中，例如 \(55-50=5\) ，可以放入编号为5的桶。由于按照此种方式来来入桶每个桶里的值就是一样的，所以桶内可以存放一个数值信息，代表此处的元素有多少个(通常一个桶里存放的是一个值域范围的元素，需要存放元素的具体数值信息)。

image-20210418213046344
image-20210418213046344

入桶后每个桶中的元素数量：

image-20210418215621271
image-20210418215621271

将上面的例子排序后输出：

1
2
3
4
5
6
7
8
9
def BucketSort(nums):
    buckets = [0] * 10  # 建立桶
    for i in nums:
        buckets[i - 50] += 1   # 索引计算

    for i in range(len(buckets)):  # 输出排序后的值
        while buckets[i] != 0:
            print(i + 50)
            buckets[i] -= 1

特殊应用

给定一个整数数组 nums和两个整数 k和 t。请你判断是否存在 两个不同下标 i 和j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0 输出：true

示例 2：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false

这种问题，直接一个暴力破解，啪一下就好了：

1
2
3
4
5
6
7
8
9
def containsNearbyAlmostDuplicate(nums, k, t):
        left = 0
        right = 0
        for i in range(len(nums)):
            for j in range(i+1,min(i+1+k,len(nums))):
                if abs(nums[i]-nums[j])<=t:
                    return True
        
        return False

但是此方法的时间复杂度为\(O(nk)\)，并不快啊。

用桶排序可将时间复杂度降至\(O(n)\). 这不是一个排序问题，为了避免空间浪费，我们申请一组临时的桶，在元素遍历的过程中，创建新的桶并释放没用的桶（同时保证桶里的元素是符合要求的，在可取索引范围内的）。

对于元素 x，其影响的区间为 [x - t, x + t]。于是我们可以设定桶的大小为 t + 1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。我们遍历该序列，假设当前遍历到元素 x，那么我们首先检查 x 所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。遍历时需要不断更新桶内元素的状态，确保目前桶内的元素都是在有效的索引范围内的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def containsNearbyAlmostDuplicate(nums, k, t):
    def getIdx(u):
    	return ((u + 1) // size) - 1 if u < 0 else u // size

    map = {}
    size = t + 1
    for i,u in enumerate(nums):
    	idx = getIdx(u)
        # 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
        if idx in map:
            return True
        # 检查相邻的桶
        l, r = idx - 1, idx + 1
        if l in map and abs(u - map[l]) <= t:
            return True
        if r in map and abs(u - map[r]) <= t:
            return True
        # 建立目标桶
        map[idx] = u
        # 维护个数为k
        if i >= k:
            map.pop(getIdx(nums[i-k]))
    return False

结语

桶排序，对于值域范围不大的排序问题来说，是一个上乘之选。