搞笑图片网站源码,百度pc权重,高职图书馆网站建设大赛,北京出啥大事了今天堆排序详解
堆排序#xff08;Heap Sort#xff09;是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质#xff08;最大堆或最小堆#xff09;来实现排序。堆排序分为两个主要步骤#xff1a;建堆和排序。 1. 什么是堆#xff1f;
堆是一种特殊的完全二叉…堆排序详解
堆排序Heap Sort是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质最大堆或最小堆来实现排序。堆排序分为两个主要步骤建堆和排序。 1. 什么是堆
堆是一种特殊的完全二叉树分为两种
最大堆每个节点的值都大于或等于其子节点的值。最小堆每个节点的值都小于或等于其子节点的值。
在堆排序中通常使用最大堆。 2. 堆排序的步骤
步骤1建堆
将待排序的数组看作一个完全二叉树。从最后一个非叶子节点开始逐步调整每个子树使其满足最大堆的性质。调整的过程称为堆化Heapify 比较当前节点与其左右子节点找到最大值。如果最大值不是当前节点则交换它们的位置。继续向下调整直到子树满足最大堆的性质。
步骤2排序
将堆顶元素最大值与数组的最后一个元素交换此时最大值已经放到正确的位置。排除最后一个元素对剩余的堆重新进行堆化使其再次满足最大堆的性质。重复上述过程直到堆中只剩下一个元素。 3. 堆排序的特点
时间复杂度
建堆( O(n) )排序每次堆化需要 ( O(\log n) )总共需要 ( n-1 ) 次堆化因此排序的时间复杂度为 ( O(n \log n) )。总时间复杂度( O(n \log n) )
空间复杂度
堆排序是原地排序算法不需要额外的存储空间空间复杂度为 ( O(1) )。
稳定性
堆排序是不稳定的排序算法因为在交换堆顶元素和最后一个元素时可能会改变相同元素的相对顺序。 4. 堆排序的优缺点
优点
时间复杂度稳定最坏情况下也是 ( O(n \log n) )。不需要额外的存储空间适合内存受限的环境。
缺点
不稳定排序可能改变相同元素的相对顺序。在实际应用中由于频繁的交换操作堆排序的常数因子较大性能可能不如快速排序或归并排序。 5. 堆排序的应用场景
适合需要排序大规模数据的场景尤其是对内存使用有严格限制的环境。常用于实现优先队列。 总结
堆排序是一种高效的排序算法通过构建最大堆并逐步提取最大值来实现排序。虽然它的时间复杂度较好但由于其不稳定性和较大的常数因子在实际应用中需要根据具体需求选择是否使用。堆排序通过建堆和排序两个步骤逐步将最大值放到数组末尾最终实现排序。它的时间复杂度为O(nlogn)是一种高效的排序算法。
堆排序详解结合例子和图形
我们通过一个具体的例子和图形来讲解堆排序的过程。
例子
假设我们有一个待排序的数组 [4, 10, 3, 5, 1] 我们的目标是将这个数组按升序排列。
步骤1建堆
将数组看作一个完全二叉树 4/ \10 3/ \5 1目标
将这个二叉树调整为最大堆每个节点的值都大于或等于其子节点的值。
调整过程 (1) 从最后一个非叶子节点开始节点 10。 (2) 比较节点 10 和其子节点 5 和 1发现 10 已经是最大值无需调整。 (3) 调整节点 4 比较节点 4 和其子节点 10 和 3发现 10 是最大值。 交换 4 和 10。 调整后的树 10/ \4 3/ \
5 1(4) 继续调整节点 4 比较节点 4 和其子节点 5 和 1发现 5 是最大值。 交换 4 和 5。 调整后的树 10/ \5 3/ \
4 1现在树已经是一个最大堆。 步骤2排序
目标将堆顶元素最大值放到数组末尾并逐步缩小堆的范围。
排序过程 (1) 将堆顶元素 10 与最后一个元素 1 交换 [1, 5, 3, 4, 10] 树结构 1/ \5 3/4(2) 排除最后一个元素 10对剩余部分重新堆化 调整节点 1 比较节点 1 和其子节点 5 和 3发现 5 是最大值。 交换 1 和 5。 调整后的树 5/ \1 3/
4继续调整节点 1 比较节点 1 和其子节点 4发现 4 是最大值。 交换 1 和 4。 调整后的树 5/ \4 3/
1(3) 将堆顶元素 5 与最后一个元素 1 交换 [1, 4, 3, 5, 10] 树结构 1/ \4 3(4) 排除最后一个元素 5对剩余部分重新堆化 调整节点 1 比较节点 1 和其子节点 4 和 3发现 4 是最大值。 交换 1 和 4。 调整后的树 4/ \
1 3(5) 将堆顶元素 4 与最后一个元素 3 交换
[3, 1, 4, 5, 10]
树结构 3/1(6) 排除最后一个元素 4对剩余部分重新堆化 调整节点 3 比较节点 3 和其子节点 1发现 3 已经是最大值。 无需调整。 (7) 将堆顶元素 3 与最后一个元素 1 交换 [1, 3, 4, 5, 10]
最终结果
数组已经按升序排列 [1, 3, 4, 5, 10]
图形总结 (1) 初始数组 [4, 10, 3, 5, 1] (2) 建堆后 [10, 5, 3, 4, 1] (3) 排序过程 每次将堆顶元素放到数组末尾并重新堆化。 (4) 最终结果
[1, 3, 4, 5, 10]
示例代码
def heapify(arr, n, i):堆化函数调整以 i 为根的子树使其满足最大堆的性质。:param arr: 待排序的数组:param n: 堆的大小:param 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):堆排序函数:param arr: 待排序的数组n len(arr)# 步骤1建堆# 从最后一个非叶子节点开始逐步调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 步骤2排序# 将堆顶元素最大值与数组末尾元素交换并重新堆化for i in range(n - 1, 0, -1):arr[0], arr[i] arr[i], arr[0] # 将最大值放到数组末尾heapify(arr, i, 0) # 重新堆化剩余部分# 示例
arr [4, 10, 3, 5, 1]
print(排序前:, arr)
heap_sort(arr)
print(排序后:, arr)© 著作权归作者所有
