堆排序和计数排序是两种高效的排序算法,用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍堆排序和计数排序的基本原理,并通过实例代码演示它们的应用。
😃😄 ❤️ ❤️ ❤️
堆排序是一种基于堆数据结构的排序算法,它将列表构建成一个二叉堆,并通过不断移除堆顶元素来得到有序列表。堆排序的核心思想是利用堆数据结构的特性,使得每次移除堆顶元素后,剩余元素仍然构成一个合法的堆。
堆排序的主要优点是稳定且效率高,时间复杂度为 O ( n log n ),适用于处理大规模数据的排序。
def heapify(arr, n, i):
largest = i # 初始化最大元素的索引
left_child = 2 * i + 1
right_child = 2 * i + 2
# 判断左子节点是否大于根节点
if left_child < n and arr[i] < arr[left_child]:
largest = left_child
# 判断右子节点是否大于根节点
if right_child < n and arr[largest] < arr[right_child]:
largest = right_child
# 如果最大元素不是根节点,则交换它们,并继续堆化
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 依次移除堆顶元素,并进行堆化
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交换堆顶元素和最后一个元素
heapify(arr, i, 0) # 对剩余元素进行堆化
# 测试堆排序
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("堆排序结果:", arr)
代码解释:上述代码演示了使用堆排序对一个列表进行排序的实例。堆排序首先将列表构建成一个最大堆,然后不断移除堆顶元素,将其放在有序部分的末尾,并继续堆化剩余元素。通过使用 heapify
函数来维护堆的性质。
计数排序是一种非比较排序算法,它通过统计列表中每个元素的出现次数,然后根据统计结果将元素放回原来的位置,从而得到有序列表。
计数排序的主要优点是适用于排序范围较小的整数列表,时间复杂度为 O ( n + k ),其中 n 为列表长度, k 为列表中元素的最大值减去最小值。
def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
# 统计列表中每个元素的出现次数
count = [0] * range_val
for num in arr:
count[num - min_val] += 1
# 根据统计结果构建有序列表
sorted_arr = []
for i in range(range_val):
for j in range(count[i]):
sorted_arr.append(i + min_val)
return sorted_arr
# 测试计数排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = counting_sort(arr)
print("计数排序结果:", sorted_arr)
代码解释:上述代码演示了使用计数排序对一个列表进行排序的实例。计数排序通过统计列表中每个元素的出现次数,然后根据统计结果构建有序列表。通过遍历统计数组,将元素放回原来的位置,实现了计数排序算法。
堆排序和计数排序都是高效的排序算法,它们分别适用于不同类型的排序需求:
本篇博客介绍了堆排序和计数排序两种高效的排序算法。堆排序通过构建最大堆,不断移除堆顶元素得到有序列表;计数排序通过统计元素出现次数,将元素放回原来的位置得到有序列表。
这两种排序算法在处理大规模数据和排序范围较小的整数列表时都有较高的效率,根据具体情况选择合适的排序算法对于提高程序性能非常重要。