算法学习2——排序算法（2）

上一篇介绍了几种常见且使用较多的排序算法，本章主要是一个进阶内容，介绍三个较为复杂的算法。

计数排序 (Counting Sort)

计数排序是一种适用于范围较小的整数序列的排序算法。它通过统计每个元素的出现次数，然后依次输出元素，实现排序。

原理

1. 找到数组中最大和最小的元素值。
2. 创建一个计数数组，其长度为最大值减去最小值加1，用于记录每个元素的出现次数。
3. 遍历输入数组，更新计数数组中的对应元素的计数。
4. 遍历计数数组，按顺序将元素填回原数组。

代码实现

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

# 测试
arr = [4, 2, 2, 8, 3, 3, 1]
print("Sorted array:", counting_sort(arr))

基数排序 (Radix Sort)

基数排序是一种非比较的整数排序算法，通过逐位排序实现排序，适用于整数或字符串。它依赖于稳定的子排序算法（如计数排序）。

原理

1. 从最低有效位到最高有效位对数组进行排序。
2. 每次排序时使用一个稳定的排序算法，如计数排序。

代码实现

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    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_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10
    return arr

# 测试
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Sorted array:", radix_sort(arr))

桶排序 (Bucket Sort)

桶排序通过将元素分配到不同的桶中，再对每个桶内部进行排序，最后将所有桶中的元素合并得到有序序列。

原理

1. 创建若干个桶（列表），每个桶存放一定范围的元素。
2. 将元素分配到相应的桶中。
3. 对每个桶中的元素进行排序（可以使用其他排序算法或递归地使用桶排序）。
4. 将所有桶中的元素合并起来，得到排序后的序列。

代码实现

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

    min_value, max_value = min(arr), max(arr)
    bucket_count = (max_value - min_value) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        buckets[(num - min_value) // bucket_size].append(num)

    sorted_array = []
    for bucket in buckets:
        sorted_array.extend(sorted(bucket))

    return sorted_array

# 测试
arr = [42, 32, 33, 52, 37, 47, 51]
print("Sorted array:", bucket_sort(arr))

总结

每种排序算法都有其适用的场景和优缺点，选择合适的排序算法对于提高程序的性能和效率有着十分关键的作用。