Bucket Sort (桶排序)

Bucket Sort Alias: 基数排序（radix sort

属于 “分配式排序”（distribution sort）

Correct Version

# pyton 实现
#!/usr/bin/env python
#encoding=utf-8

import math
import itertools

def maximumGap(self, nums: List[int]) -> int:
        n_max, n_min = max(nums), min(nums)
        byte_max, byte_min = math.ceil(n_max.bit_length() / 8), math.floor(n_min.bit_length() / 8)
        for i in range(byte_max):
            if i < byte_min - 1:
                continue
            i_8 = i * 8
            byte_check = 0xFF << i_8
            buckets = [[] for _ in range(256)]
            for num in nums:
                buckets[(num & byte_check) >> i_8].append(num)
            nums = list(itertools.chain.from_iterable(buckets))
        pre_num, res_no = nums[0], 0
        for num in nums[1:]:
            if res_no < (i := num - pre_num):
                res_no = i
            pre_num = num
        return res_no

Incomplete correct version (Only for reference)

What’s wrong with this version?

• It cannot deal with [1,100000], [1,10000,1000000,100].etc

Implementation

# pyton 实现
#!/usr/bin/env python
#encoding=utf-8

import math

def sort(a, radix=10):
    """a为整数列表， radix为基数"""
    K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
    bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    for i in range(1, K+1): # K次循环
        for val in a:
            bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 （从低到高）
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并
        bucket = [[] for i in range(radix)]

关键点解释(Explanation of key):

1. math.log(max(a), radix)
   • math.log(max(a), radix) 部分用于计算数组 a 中最大值以 radix 进制表示所需要的最小位数
   • 在基数排序算法中， radix 参数代表的是所采用的基数，即我们通常所说的进制数。例如，当 radix 为 10 时，表示使用十进制进行排序；若 radix 为 2 ，则表示使用二进制进行排序。
   • 

Code explanation

1. math.log(max(a), radix)部分用于计算数组a中最大值以radix进制表示所需要的最小位数。
2. 初始化一个长度为radix的空桶列表bucket，用于在每一轮迭代中存放对应每一位数值的元素。
3. 循环K次，K为所需的最大位数。在每一次循环中：
4. 遍历数组a中的每个元素，通过取模和除法操作来获取当前处理位上的数值，并将其放入对应的桶中。
5. 清空原数组a，然后按照桶的顺序合并回原数组，这样就完成了对当前位的排序。
6. 最终经过K轮循环后，数组a将被完全排序。

关于该排序的更多内容(More)