13 高级排序算法之堆排序的原理与实现

在上一篇文章中,我们探讨了动态规划与数据结构结合的实例分析,了解了最优子结构的概念。今天,我们将深入研究另一种高级排序算法:堆排序。堆排序是一种基于的数据结构进行排序的算法,通过利用完全二叉树的性质来完成排序操作。

堆的基本概念

在深入堆排序之前,让我们先回顾一下什么是。堆是一种特殊的完全二叉树,每个节点值的特性如下:

  • 最大堆:每个父节点的值都大于或等于其子节点的值。
  • 最小堆:每个父节点的值都小于或等于其子节点的值。

在堆排序中,我们主要使用最大堆来实现升序排序。构造最大堆的过程使得堆的最大元素始终位于根节点。

堆排序的基本步骤

堆排序的过程主要可以分为两个步骤:

  1. 构建最大堆:从最后一个非叶子节点开始,自下而上逐步调整,使得每个子树都满足最大堆的条件。
  2. 排序操作:将根节点(最大值)与最后一个元素交换位置,然后缩小堆的存储范围(即去掉最后一个元素),再对新的根节点进行堆调整,以保持最大堆的性质。重复这个过程直到所有元素都有序。

堆排序的实现

下面我们提供一个堆排序的实现示例,使用 Python 来演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def heapify(arr, n, i):
largest = i # 初始化最大的节点为根节点
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点

# 如果左子节点比根节点大
if left < n and arr[left] > arr[largest]:
largest = left

# 如果右子节点比当前最大的节点大
if right < n and arr[right] > arr[largest]:
largest = right

# 如果最大的不是根节点,交换它
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 = [3, 5, 1, 10, 2, 7]
heap_sort(arr)
print("排序后的数组:", arr)

例子分析

假设我们有一个数组 arr = [3, 5, 1, 10, 2, 7],经过堆排序的步骤如下:

  1. 构建最大堆

    • 最初,数组的最大堆形态可能是 [10, 5, 7, 3, 2, 1]
    • 这个过程就是通过不断调用 heapify 函数调整数组,使其符合最大堆的特性。
  2. 提取元素并排序

    • 第一步,10(最大值)与 1 交换,数组变成 [1, 5, 7, 3, 2, 10],然后再次进行堆化。
    • 重复这个过程,最终将数组调整为 [1, 2, 3, 5, 7, 10]

堆排序的时间复杂度

  • 构建最大堆:时间复杂度为 $O(n)$。
  • 排序操作:每次调整的时间复杂度为 $O(\log n)$,共需要执行 $n$ 次,所以总的时间复杂度为 $O(n \log n)$。

此外,堆排序是不稳定的排序算法,因为在排序过程中可能会改变相同元素的相对顺序。

总结

堆排序是一种高效的排序算法,尤其是在大数据集下表现优越。在本篇文章中,我们深入探讨了堆的基本原理、堆排序的步骤以及实现代码。下一篇文章中,我们将讨论另一类高级排序算法:桶排序基数排序,它们各自的应用场景和优缺点。更多的实践将帮助我们将这些理论应用到实际问题中去,充分掌握高级排序算法的精髓。

13 高级排序算法之堆排序的原理与实现

https://zglg.work/datastructure-one/13/

作者

AI免费学习网(郭震)

发布于

2024-08-11

更新于

2024-08-12

许可协议

分享转发

复习上节

交流

更多教程加公众号

更多教程加公众号

加入星球获取PDF

加入星球获取PDF

打卡评论