【算法】堆排序算法的讲解和代码实践

程序员 · 2024-9-21 21:35:39

思绪

学习堆排序之前，先简朴先容一下什么是堆。
但是要相识堆，还得先连接二叉树。
二叉树，就是每个节点最多有两个子节点的树形的数据布局。二叉树又有完全二叉树、满二叉树等等，细的就不讲了，可以搜一下资料，还是许多讲这个的。
二叉堆，它是属于完全二叉树，同时它又满意堆的性子（子节点的值总是小于它的父节点（也可以是大于））。也就是说，根节点肯定是最大（也大概是最小）的谁人元素。
堆排序就是根据这个特点，把数组当作是一个二叉堆，每次计算出一个最大或最小值然后举行排序的。
那么完全二叉树它怎么跟数组关联上呢？其实完全二叉树它有一个特点，就是它完全可以用数组来体现。具体的这里就不讲了，但是有几点需要记着。

末了一个非叶子节点下标 = 数组长度 ÷ 2 - 1；
非叶子节点的左子节点下标 = 该节点下标 × 2 + 1；
非叶子节点的右子节点下标 = 该节点下标 × 2 + 2。

知道这三点之后，我们就可以根据完全二叉树的性子，把它编程一个二叉堆，然后举行排序了。
关于满二叉树和完全二叉树我还是简朴画个图吧，资助明确。

这种就叫满二叉树，左右完全平衡，非叶子节点都有两个子节点，叶子节点都在一层。
完全二叉树就是说，满二叉树的根本上，好比说要加一个节点，那么只能先在D下面加，然后依次今后。要删除一个节点，只能从右下角开始，先把G删掉，再删F，再删E如许。

那么完全二叉树跟数组的关系呢？我们加一个数组看一下：

就可以看到了，好比末了一个非叶子节点是C，下标为2，数组长度是6，6 ÷ 2 - 1 = 2，就印证了上面的公式。
OK二叉树讲的有点多了，下面进入团体，开始将堆排序。
讲解

依然是有如许一个数组：

那么我们先把它当作一个完全二叉树，开始把它构建成一个最大堆，第一步，找到末了一个非叶子节点，用上面的公式，数组长度为8，末了一个非叶子节点就是 8 ÷ 2 - 1 = 3，那么末了一个非叶子节点就找到了。末了一个非叶子节点前面的元素，都优劣叶子节点，我们用蓝色标记出来：

找到非叶子节点之后，我们从末了一个非叶子节点开始向前遍历全部的非叶子节点。
先看末了一个非叶子节点 -15 ，它是否小于它的两个（也大概是一个）叶子节点。根据公式计算，计算出它的两个叶子下标分别为：3 × 2 + 1 = 7，3 × 2 + 2 = 8，下标为8的元素很显然不存在，那么 -15 只需要跟22对比，显着 -15 小于 22，互换两个元素的位置：

然后遍历 14，14 的两个子节点下标为 2 × 2 + 1 = 5，2 × 2 + 2 = 6，以是 14 需要与 324 和 1 举行对比，14 比 324 小，互换位置：

324 与 1 比，324 大，不再互换。
下面轮到 -3。-3 的两个子节点下标为 1 × 2 + 1 = 3，1 × 2 + 2 = 4，-3 与 22、0 对比。-3 小于 22，互换位置：

22 比 0 大，不再互换。
下一步，26，两个子节点为 1、 2，26 与 22、324 对比。比 22 大，不互换，比 324 小，互换：

如许就形成了一个最大堆，每一个非叶子节点都大于它自己的叶子节点。最大值就在根节点，也就是我们数组下标为 0 的位置。接下来，我们把最大的数与数组末了一个元素互换位置：

如许最大的数就跑到了数组的末了，第一轮的排序也就竣事了。
那么第二轮，我们将已排好序的大数清除到构建最大堆的范围之外，只用前面7个数去构件最大堆，构建完成之后，再把最大数挪到下标6的位置，以此类推，即可完成整个数组的排序。
实现

【算法】堆排序算法的讲解和代码实践

所属分类: 问答交流

新帖推荐: 30日

推荐作品