2 桶排序与基数排序

在上一篇中，我们探讨了归并排序与快速排序的优化，这些算法在大多数情况下表现卓越，但在某些特定条件下，我们可能需要使用其他排序算法来满足特定的需求。本篇将深入探讨桶排序与基数排序这两种进阶排序算法，分析它们的原理、实现过程以及各自的适用场景。

桶排序

原理

桶排序（Bucket Sort）是一种分配排序，特别适用于数据均匀分布的情况。它的基本思想是把数据分到有限数量的“桶”中，再分别对每个桶内的数据进行排序，最后将所有桶中的数据合并。

步骤

1. 创建桶：根据待排序数据的范围创建 n 个桶。
2. 分配数据：遍历待排序数据，将每个数据放入相应的桶中。
3. 桶内排序：对每个非空桶使用其他排序算法（如快速排序或插入排序）进行排序。
4. 合并桶：将所有桶中的数据依次合并，形成有序的结果。

代码示例

以下是 Python 实现 桶排序 的示例：

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

    # 1. 创建桶
    min_value = min(array)
    max_value = max(array)
    bucket_count = max_value - min_value + 1
    buckets = [[] for _ in range(bucket_count)]

    # 2. 分配数据
    for num in array:
        buckets[num - min_value].append(num)

    # 3. 桶内排序及合并
    sorted_array = []
    for bucket in buckets:
        if bucket:
            sorted_array.extend(sorted(bucket))  # 使用内置的 sorted 函数

    return sorted_array

# 示例
data = [3, 6, 2, 8, 4, 5, 7, 1]
print(bucket_sort(data))

适用场景

桶排序在以下情况下表现良好：

• 数据范围较小且均匀分布。
• 对于需要进行大量相同值的比较时，桶排序的性能会优於其他算法。

然而，桶排序的缺点在于它对环境要求较高，桶的数量和数据分布都对算法的性能有很大的影响。

基数排序

原理

基数排序（Radix Sort）是一种非比较排序算法，主要通过对数字的每一位进行多次排序来实现。对每个数进行 LSD（Least Significant Digit） 或 MSD（Most Significant Digit） 的排序。

步骤

1. 从最低位（或最高位）开始进行排序。
2. 使用 桶排序 对每一位进行排序。
3. 重复上述过程，直到所有位都排序完成。

代码示例

以下是基于 桶排序 的 基数排序 实现：

def counting_sort_on_digit(array, exp):
    output = [0] * len(array)
    count = [0] * 10

    # 统计每个数字出现的频次
    for num in array:
        index = (num // exp) % 10
        count[index] += 1

    # 更新计数数组
    for i in range(1, 10):
        count[i] += count[i - 1]

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

    return output

def radix_sort(array):
    max_value = max(array)
    exp = 1  # 初始化为个位

    while max_value // exp > 0:
        array = counting_sort_on_digit(array, exp)
        exp *= 10

    return array

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

适用场景

基数排序适合以下情况：

• 数字范围较小的整数序列。
• 需要高效处理大量数字数据，而不局限于使用内置比较排序的情况。

小结

在这篇文章中，我们深入探讨了 桶排序 和 基数排序 两种先进的排序算法。两者在特定场景下具有优越的性能，而它们的实现也各具特色。在了解了这些算法的基本原理与实现后，下一篇将与大家讨论更高级排序算法的比较，以及如何根据问题选择最合适的排序策略。