前言

非比较排序算法是一类排序方法，它们不通过直接比较元素的大小来进行排序，而是利用一些其他的技巧和数据结构来实现排序。

计数排序（Counting Sort）

计数排序适用于非负整数排序，它基于元素的频次统计。它的思想是创建一个计数数组来存储每个元素出现的次数，然后根据计数数组重建排序结果。

def counting_sort(arr):
    max_val = max(arr)
    count_arr = [0] * (max_val + 1)
    for num in arr:
        count_arr[num] += 1
    sorted_arr = []
    for i in range(len(count_arr)):
        sorted_arr.extend([i] * count_arr[i])
    return sorted_arr
# 测试数据
test_data = [4, 2, 2, 8, 3, 3, 1]
sorted_data = counting_sort(test_data)
print(sorted_data)

桶排序（Bucket Sort）

桶排序将元素分散到不同的桶中，每个桶内部使用其他排序方法（通常是插入排序），然后按顺序合并桶的结果得到排序结果。

def bucket_sort(arr, num_buckets):
    min_val = min(arr)
    max_val = max(arr)
    bucket_range = (max_val - min_val) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    for num in arr:
        index = int((num - min_val) // bucket_range)
        buckets[index].append(num)
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    return sorted_arr
# 测试数据
test_data = [0.42, 0.32, 0.85, 0.17, 0.05, 0.72]
sorted_data = bucket_sort(test_data, num_buckets=5)
print(sorted_data)

基数排序（Radix Sort）

基数排序适用于整数排序，它按照数字的位数依次进行排序。可以从最低位（LSD）或最高位（MSD）开始。

def radix_sort_lsd(arr):
    max_digit = len(str(max(arr)))
    for digit in range(max_digit):
        buckets = [[] for _ in range(10)]
        for num in arr:
            digit_val = (num // 10**digit) % 10
            buckets[digit_val].append(num)
        arr = [num for bucket in buckets for num in bucket]
    return arr
# 测试数据
test_data = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_data = radix_sort_lsd(test_data)
print(sorted_data)

LSD（Least Significant Digit）基数排序

LSD基数排序从数字的最低位（个位）开始，依次将数字分配到10个桶中，然后按照桶的顺序重新组合数字。这个过程会重复执行，直到处理完最高位为止。LSD基数排序适用于所有位数相同的数字，例如整数。

def counting_sort(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]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort_lsd(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
# 测试数据
test_data = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort_lsd(test_data)
print(test_data)

MSD（Most Significant Digit）基数排序：

MSD基数排序从数字的最高位（千位、百位等）开始，根据当前位的值将数字分配到桶中，然后对每个桶内的数字递归地进行排序。这个过程会逐渐降低到低位，直到处理完最低位为止。MSD基数排序适用于不同位数的数字，但要处理好位数不同的情况。

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort_msd(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
# 测试数据
test_data = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort_msd(test_data)
print(test_data)

非比较排序总结：

非比较排序算法是一类不基于元素比较的排序方法，它们通常在特定条件下具有高效性能。以下是三种非比较排序方法（计数排序、桶排序和基数排序）的总结：

计数排序：

适用于非负整数。
基于元素的频次统计。
通过计数数组重建排序结果。
时间复杂度为O(n + k)，其中n是元素数量，k是计数数组的大小。

桶排序：

适用于均匀分布的数据。
将元素分散到不同的桶中，桶内使用其他排序方法。
桶的数量和选择的内部排序算法会影响性能。
平均时间复杂度取决于桶的数量和内部排序算法。

基数排序：

适用于整数，可以处理位数不同的数字。
分为LSD和MSD两种策略。
通过按位排序，逐渐达到整体排序效果。
时间复杂度与数字位数和元素数量有关。
非比较排序算法的优点在于它们可以在特定条件下实现线性时间复杂度，不受元素比较的影响。然而，它们可能需要更多的内存空间，对于特定类型的数据，有时可能不如一些比较排序算法（如快速排序）效率高。在实际应用中，选择合适的排序算法要根据数据的特点和性能需求进行权衡。

非比较排序

前言