Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

什么是分配排序法

分配排序法是一种基于各种数据分布特性和信息量的统计推测方法，通过计数完成排序过程。分配排序法是不基于比较的排序方法，排序效率很高。

常见的分配排序法示例

• 桶排序
• 基数排序

下面将对这两种排序进行详细说明。

桶排序

桶排序的思想是把数据分到有限数量的桶里。每个桶再分别进行排序。也就是说，假设输入数据服从均匀分布，将数据平均分配到 k 个桶中，每个桶再分别排序。

具体实现过程：

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

下面是Python代码：

def bucket_sort(arr, bucketSize=5):
    if len(arr) == 0:
        return arr

    minValue = arr[0]
    maxValue = arr[0]
    for i in range(1, len(arr)):
        if arr[i] < minValue:
            minValue = arr[i]
        elif arr[i] > maxValue:
            maxValue = arr[i]

    # 根据最大值与最小值计算桶的数量
    bucketCount = int((maxValue - minValue) / bucketSize) + 1
    buckets = []
    for i in range(bucketCount):
        buckets.append([])

    # 将数据放到桶中
    for i in range(len(arr)):
        buckets[int((arr[i] - minValue) / bucketSize)].append(arr[i])

    arr = []
    for i in range(len(buckets)):
        quick_sort(buckets[i])
        for j in range(len(buckets[i])):
            arr.append(buckets[i][j])

    return arr

基数排序

基数排序是按照数字的低位先排序，然后由低位次高位，依次排序到最高位。因此，基数排序方法适用于对较长的数列进行排序。

具体实现过程：

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用桶排序或计数排序都可以）；

下面是Python代码：

def radix_sort(arr):
    radix, digit = 10, 1
    max_num = max(arr)

    while max_num >= digit:
        bucket_list = [[] for _ in range(radix)]
        for i in arr:
            bucket_list[int((i/digit)%10)].append(i)

        arr.clear()
        for i in bucket_list:
            arr += i

        digit *= radix

    return arr

示例说明

示例1：桶排序

对于输入数组[3, 1, 5, 2, 7, 6, 4, 8, 9, 10]，使用桶排序得到的输出为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

示例2：基数排序

对于输入数组[753, 758, 12, 15, 32, 36, 369]，使用基数排序得到的输出为：

[12, 15, 32, 36, 369, 753, 758]

总结

分配排序法虽然不基于比较，但排序效率极高，特别适用于数据分布比较均匀的情况。桶排序和基数排序是其中两个比较常用的算法，掌握了这两个算法，可以对常见的数据排序问题快速得到解决。