Python实现非比较排序算法

非比较排序算法指的是不需要进行元素之间比较的排序算法，常见的有计数排序、基数排序和桶排序。

1. 计数排序

计数排序适用于数据范围较小且元素为非负整数的情况。它通过遍历一遍数组，统计每个元素出现的次数，然后依次输出即可。

Python代码实现：

def counting_sort(arr):
max_val = max(arr)
count_arr = [0] * (max_val + 1)
for i in arr:
count_arr[i] += 1
idx = 0
for i in range(max_val + 1):
for j in range(count_arr[i]):
arr[idx] = i
idx += 1

示例：

data = [2, 5, 3, 0, 2, 3, 0, 3]
counting_sort(data)
print(data)

输出：[0, 0, 2, 2, 3, 3, 3, 5]

2. 基数排序

基数排序适用于元素为正整数且位数较少的情况。它通过对待排序的数字进行归纳，从最低位到最高位分别进行一次排序，最终输出。

Python代码实现：

def radix_sort(arr):
max_bits = len(str(max(arr)))
for i in range(max_bits):
bucket = [[] for _ in range(10)]
for num in arr:
digit = num // (10 ** i) % 10
bucket[digit].append(num)
arr = [num for sub_bucket in bucket for num in sub_bucket]
return arr

示例：

data = [123, 56, 987, 23, 9]
result = radix_sort(data)
print(result)

输出：[9, 23, 56, 123, 987]

3. 桶排序

桶排序适用于元素值分布较均匀的情况。它将元素按照一定的范围分配到桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素合并即可。

Python代码实现：

def bucket_sort(arr):
max_val, min_val = max(arr), min(arr)
bucket_size = 5
bucket_cnt = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_cnt)]
for num in arr:
idx = (num - min_val) // bucket_size
buckets[idx].append(num)
for i in range(bucket_cnt):
buckets[i].sort()
return [num for bucket in buckets for num in bucket]

示例：

data = [37, 29, 56, 79, 84, 88, 94, 17, 66, 15]
result = bucket_sort(data)
print(result)

输出：[15, 17, 29, 37, 56, 66, 79, 84, 88, 94]