堆排序

排序算法

堆排序是一种基于比较的高效排序算法,它利用堆这种数据结构的特性进行排序,通过建立最大堆,不断取出最大元素并调整堆来实现排序。

时间复杂度:最佳 O(n log n) | 平均 O(n log n) | 最差 O(n log n)
空间复杂度:O(1)
稳定性:不稳定

应用场景/前提条件

  • 对大规模数据效率高
  • 不需要额外空间
  • 保证最坏情况时间复杂度为O(n log n)

算法讲解

介绍

堆排序(Heap Sort)是一种高效的原地排序算法,它巧妙地利用了“堆”数据结构。其核心思想是首先将待排序的数组重构成一个最大堆(Max Heap)。在最大堆中,根节点(数组的第一个元素)始终是所有元素中的最大值。

构建好最大堆后,算法将堆顶的最大元素与堆末尾的元素交换,从而将当前的最大值放置到数组的正确最终位置。接着,将堆的大小减一,并对剩余的元素进行“堆化”调整,确保新的根节点仍然是剩余元素中的最大值。此过程不断重复——交换、缩小堆、重新堆化——直到所有元素都被放置到其最终的有序位置,完成整个排序。

堆(Heap)是一种特殊的完全二叉树结构,它的两个重要特性:

  • 堆是一个完全二叉树,除了最底层外,其他层的节点都是满的,最底层的节点从左到右填充。
  • 在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都小于或等于其子节点的值。

堆的数组表示:

虽然堆是一种树结构,但是也可以用数组高效地表示,这是堆的一个重要特性。

对于数组中索引为 i 的节点:

其左子节点的索引为 2*i + 1

其右子节点的索引为 2*i + 2

...