idc新人如何做自己的网站,ftp怎么上传wordpress,wordpress生成推广链接,做娱乐自媒体有哪些网站可以推荐上一篇介绍了几种常见且使用较多的排序算法#xff0c;本章主要是一个进阶内容#xff0c;介绍三个较为复杂的算法。
计数排序 (Counting Sort)
计数排序是一种适用于范围较小的整数序列的排序算法。它通过统计每个元素的出现次数#xff0c;然后依次输出元素#xff0c;…上一篇介绍了几种常见且使用较多的排序算法本章主要是一个进阶内容介绍三个较为复杂的算法。
计数排序 (Counting Sort)
计数排序是一种适用于范围较小的整数序列的排序算法。它通过统计每个元素的出现次数然后依次输出元素实现排序。
原理
找到数组中最大和最小的元素值。创建一个计数数组其长度为最大值减去最小值加1用于记录每个元素的出现次数。遍历输入数组更新计数数组中的对应元素的计数。遍历计数数组按顺序将元素填回原数组。
代码实现
def counting_sort(arr):if len(arr) 0:return arrmin_val min(arr)max_val max(arr)range_of_elements max_val - min_val 1count_arr [0] * range_of_elementsoutput_arr [0] * len(arr)for num in arr:count_arr[num - min_val] 1for 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] numcount_arr[num - min_val] - 1return output_arr# 测试
arr [4, 2, 2, 8, 3, 3, 1]
print(Sorted array:, counting_sort(arr))基数排序 (Radix Sort)
基数排序是一种非比较的整数排序算法通过逐位排序实现排序适用于整数或字符串。它依赖于稳定的子排序算法如计数排序。
原理
从最低有效位到最高有效位对数组进行排序。每次排序时使用一个稳定的排序算法如计数排序。
代码实现
def counting_sort_for_radix(arr, exp):n len(arr)output [0] * ncount [0] * 10for i in range(n):index arr[i] // expcount[index % 10] 1for i in range(1, 10):count[i] count[i - 1]for i in range(n - 1, -1, -1):index arr[i] // expoutput[count[index % 10] - 1] arr[i]count[index % 10] - 1for i in range(n):arr[i] output[i]def radix_sort(arr):max_val max(arr)exp 1while max_val // exp 0:counting_sort_for_radix(arr, exp)exp * 10return arr# 测试
arr [170, 45, 75, 90, 802, 24, 2, 66]
print(Sorted array:, radix_sort(arr))桶排序 (Bucket Sort)
桶排序通过将元素分配到不同的桶中再对每个桶内部进行排序最后将所有桶中的元素合并得到有序序列。
原理
创建若干个桶列表每个桶存放一定范围的元素。将元素分配到相应的桶中。对每个桶中的元素进行排序可以使用其他排序算法或递归地使用桶排序。将所有桶中的元素合并起来得到排序后的序列。
代码实现
def bucket_sort(arr, bucket_size5):if len(arr) 0:return arrmin_value, max_value min(arr), max(arr)bucket_count (max_value - min_value) // bucket_size 1buckets [[] 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))总结
每种排序算法都有其适用的场景和优缺点选择合适的排序算法对于提高程序的性能和效率有着十分关键的作用。
