赞
踩
上一篇介绍了几种常见且使用较多的排序算法,本章主要是一个进阶内容,介绍三个较为复杂的算法。
计数排序是一种适用于范围较小的整数序列的排序算法。它通过统计每个元素的出现次数,然后依次输出元素,实现排序。
原理
代码实现
- 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))

基数排序是一种非比较的整数排序算法,通过逐位排序实现排序,适用于整数或字符串。它依赖于稳定的子排序算法(如计数排序)。
原理
代码实现
- 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))

桶排序通过将元素分配到不同的桶中,再对每个桶内部进行排序,最后将所有桶中的元素合并得到有序序列。
原理
代码实现
- 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))

总结
每种排序算法都有其适用的场景和优缺点,选择合适的排序算法对于提高程序的性能和效率有着十分关键的作用。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。