当前位置:   article > 正文

算法学习2——排序算法(2)

算法学习2——排序算法(2)

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

计数排序 (Counting Sort)

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

原理

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

代码实现

  1. def counting_sort(arr):
  2. if len(arr) == 0:
  3. return arr
  4. min_val = min(arr)
  5. max_val = max(arr)
  6. range_of_elements = max_val - min_val + 1
  7. count_arr = [0] * range_of_elements
  8. output_arr = [0] * len(arr)
  9. for num in arr:
  10. count_arr[num - min_val] += 1
  11. for i in range(1, range_of_elements):
  12. count_arr[i] += count_arr[i - 1]
  13. for num in reversed(arr):
  14. output_arr[count_arr[num - min_val] - 1] = num
  15. count_arr[num - min_val] -= 1
  16. return output_arr
  17. # 测试
  18. arr = [4, 2, 2, 8, 3, 3, 1]
  19. print("Sorted array:", counting_sort(arr))

基数排序 (Radix Sort)

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

原理

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

代码实现

  1. def counting_sort_for_radix(arr, exp):
  2. n = len(arr)
  3. output = [0] * n
  4. count = [0] * 10
  5. for i in range(n):
  6. index = arr[i] // exp
  7. count[index % 10] += 1
  8. for i in range(1, 10):
  9. count[i] += count[i - 1]
  10. for i in range(n - 1, -1, -1):
  11. index = arr[i] // exp
  12. output[count[index % 10] - 1] = arr[i]
  13. count[index % 10] -= 1
  14. for i in range(n):
  15. arr[i] = output[i]
  16. def radix_sort(arr):
  17. max_val = max(arr)
  18. exp = 1
  19. while max_val // exp > 0:
  20. counting_sort_for_radix(arr, exp)
  21. exp *= 10
  22. return arr
  23. # 测试
  24. arr = [170, 45, 75, 90, 802, 24, 2, 66]
  25. print("Sorted array:", radix_sort(arr))

桶排序 (Bucket Sort)

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

原理

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

代码实现

  1. def bucket_sort(arr, bucket_size=5):
  2. if len(arr) == 0:
  3. return arr
  4. min_value, max_value = min(arr), max(arr)
  5. bucket_count = (max_value - min_value) // bucket_size + 1
  6. buckets = [[] for _ in range(bucket_count)]
  7. for num in arr:
  8. buckets[(num - min_value) // bucket_size].append(num)
  9. sorted_array = []
  10. for bucket in buckets:
  11. sorted_array.extend(sorted(bucket))
  12. return sorted_array
  13. # 测试
  14. arr = [42, 32, 33, 52, 37, 47, 51]
  15. print("Sorted array:", bucket_sort(arr))

总结

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/882365?site
推荐阅读
相关标签
  

闽ICP备14008679号