python实现计数排序、桶排序和基数排序算法

计数排序

计数排序是一种非比较排序算法，适用于元素范围较小的整数排序。它通过统计每个元素出现的次数，然后根据计数对元素进行排序。

算法步骤：

1. 找出待排序数组中的最大值和最小值。
2. 创建一个计数数组，计数数组的长度为最大值和最小值的差值加一。
3. 统计每个元素在待排序数组中出现的次数，并存储在计数数组的对应位置。
4. 对计数数组进行累加处理。
5. 根据计数数组，将元素放回到原数组的正确位置。

Python实现计数排序

def counting_sort(lst):
    if not lst:
        return []
    
    min_val = min(lst)
    max_val = max(lst)
    range_of_elements = max_val - min_val + 1
    count_arr = [0] * range_of_elements
    output_arr = [0] * len(lst)
    
    for num in lst:
        count_arr[num - min_val] += 1
    
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]
    
    for num in reversed(lst):
        output_arr[count_arr[num - min_val] - 1] = num
        count_arr[num - min_val] -= 1
    
    return output_arr

# 示例
lst = [4, 2, 2, 8, 3, 3, 1]
sorted_lst = counting_sort(lst)
print("排序后的列表:", sorted_lst)

桶排序

桶排序适用于均匀分布的浮点数。它将数据分到有限数量的桶里，对每个桶分别排序，最后合并所有桶中的数据得到有序序列。

算法步骤：

1. 设置一个定量的数组当作空桶。
2. 把数组元素分散到各个桶中。
3. 对每个不为空的桶进行排序。
4. 依次从不为空的桶中取出元素。

Python实现桶排序

def bucket_sort(lst):
    if len(lst) == 0:
        return []
    
    bucket_count = 10
    max_value = max(lst)
    buckets = [[] for _ in range(bucket_count)]
    
    for num in lst:
        index = int(num * bucket_count / (max_value + 1))
        buckets[index].append(num)
    
    for bucket in buckets:
        bucket.sort()
    
    sorted_lst = []
    for bucket in buckets:
        sorted_lst.extend(bucket)
    
    return sorted_lst

# 示例
lst = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
sorted_lst = bucket_sort(lst)
print("排序后的列表:", sorted_lst)

基数排序

基数排序是通过按位排序的方法，首先对最低位进行排序，然后对次低位进行排序，依次进行，直到最高位。基数排序适用于整数或字符串排序。

算法步骤：

1. 找出数组中的最大值，确定排序的位数。
2. 从最低位开始，对每个位进行计数排序。

Python实现基数排序

def counting_sort_for_radix(lst, exp):
    n = len(lst)
    output = [0] * n
    count = [0] * 10
    
    for num in lst:
        index = num // exp
        count[index % 10] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    for num in reversed(lst):
        index = num // exp
        output[count[index % 10] - 1] = num
        count[index % 10] -= 1
    
    for i in range(n):
        lst[i] = output[i]

def radix_sort(lst):
    max_val = max(lst)
    
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(lst, exp)
        exp *= 10
    
    return lst

# 示例
lst = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_lst = radix_sort(lst)
print("排序后的列表:", sorted_lst)

算法时间复杂度

• 计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是数组中元素的范围。适用于范围较小的整数排序。
• 桶排序的时间复杂度为O(n+k)，其中n是数组长度，k是桶的数量。适用于均匀分布的浮点数排序。
• 基数排序的时间复杂度为O(d(n+k))，其中n是数组长度，k是桶的数量，d是位数。适用于整数或字符串排序。

通过以上实现，可以看到这三种排序算法在不同场景下的适用性。计数排序适用于范围较小的整数排序；桶排序适用于均匀分布的浮点数排序；基数排序适用于多位数的整数排序。