14 高级排序算法之桶排序与基数排序

在上一篇博文中，我们探讨了堆排序的原理与实现，了解了如何利用堆数据结构来进行高效排序。今天，我们将继续深入高级排序算法的世界，重点讨论两种有趣且实用的排序算法：桶排序和基数排序。这两种算法在特定的情况下能够提供优越的排序性能，尤其是当我们处理的数据具有一定特点时。

一、桶排序

桶排序是一种分布式排序算法，它的基本思想是将待排序的数据分到有限数量的“桶”（bucket）里，再对每个桶内部进行排序，最后将所有桶中的元素合并成一个有序序列。桶排序适用于浮点数或均匀分布的整数。

1. 桶排序的步骤

1. 确定范围：选择合适的桶数目 k 和每个桶的范围。
2. 分配：将数据分配到各个桶中。
3. 排序：对每个非空的桶内部进行单独排序（可以使用其他排序算法）。
4. 合并：依次将桶中的元素合并成最终的结果。

2. 桶排序的实现

下面是一个简单的桶排序实现示例，假设我们对一组浮点数进行排序：

def bucket_sort(arr):
    if len(arr) == 0:
        return arr

    # 创建k个空桶
    k = 10  # 假设桶的数量为10
    buckets = [[] for _ in range(k)]

    # 将元素分配到对应的桶中
    for value in arr:
        index = int(value * k)  # 根据元素的值确定桶的索引
        if index >= k:  # 防止索引越界
            index = k - 1
        buckets[index].append(value)

    # 对每个桶进行排序
    for i in range(k):
        buckets[i] = sorted(buckets[i])  # 使用内置的排序

    # 合并所有桶中的元素
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

# 示例
data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.41, 0.50]
sorted_data = bucket_sort(data)
print(sorted_data)

3. 桶排序的时间复杂度与空间复杂度

桶排序的时间复杂度为 $O(n + k)$，其中 $n$ 是待排序元素的数量，$k$ 是桶的数量。在最优情况下（每个桶的元素数料平均分配），桶内部排序可以达到 $O(n/k)$。桶排序的空间复杂度为 $O(n + k)$，主要用于桶的存储。

二、基数排序

基数排序是一种非比较的整数排序算法，它通过逐位比较数字的每一位来实现排序。基数排序适用于处理非负整数以及有限范围内的数。

1. 基数排序的步骤

基数排序的基本步骤如下：

1. 确定最大数字的位数 $d$。
2. 从最低位到最高位进行稳定的排序，通常使用计数排序作为子排序算法。
3. 重复步骤2，直到所有位都排序完成。

2. 基数排序的实现

以下是基数排序的简单实现示例：

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n  # 输出数组
    count = [0] * 10  # 假设数字范围为0-9

    # 计算每个数字的出现次数
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # 累计数字出现的次数
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 构建输出数组
    for i in range(n - 1, -1, -1):
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1

    # 复制输出数组到原数组
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1  # 指数，表示当前处理的位数

    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

# 示例
data = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(data)
print(data)

3. 基数排序的时间复杂度与空间复杂度

基数排序的时间复杂度为 $O(d(n + r))$，其中 $n$ 是待排序元素的数量，$d$ 是数字的位数，$r$ 是基数。在空间复杂度方面，基数排序需要额外的 $O(n + r)$ 空间用于存储计数数组和输出数组。

总结

在本篇文章中，我们详细介绍了桶排序和基数排序两种高级排序算法，它们各自具有独特的优势和适用场景。桶排序在处理数据均匀分布时表现优异，而基数排序则在处理非负整数时能够高效运行。

随着我们对排序算法的深入理解，下一篇文章将继续为您带来 高级排序算法之合并排序的高级技巧，敬请期待！