数据结构 ——— 堆排序算法的实现

目录

前言

向下调整算法（默认建大堆）

堆排序算法的实现（默认升序）

---

前言

在之前几章学习了如何用向上调整算法和向下调整算法对数组进行建大/小堆
数据结构 ——— 向上/向下调整算法将数组调整为升/降序_对数组进行降序排序代码-CSDN博客

也学习了把向上调整算法和向下调整算法的效率作比较
比较发现：向上调整算法的效率低于向下调整算法
数据结构 ——— 向上调整建堆和向下调整建堆的区别-CSDN博客

所以接下来堆排序算法的实现通过向下调整算法来实现

---

向下调整算法（默认建大堆）

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void  AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 先找出左右孩子中大的那个if ((child + 1 < size) && (a[child + 1] > a[child]))child++;if (a[parent] < a[child]){// 交换Swap(&a[parent], &a[child]);// 迭代parent = child;child = parent * 2 + 1;}else{break;}}
}

向下调整算法调整的逻辑结构是二叉树，但是调整的物理结构是数组
也就是把数组看作二叉树利用向下调整算法来调整

所以 child 节点（左孩子）的下标 就可以通过 parent*2+1 得到
举例说明，有这样一个数组：a[] = { 1,2,5,7,9 };
数组 a 转换为二叉树为：

       1
      /  \
    2    5
   /  \
 7    9

2 节点的下标是 1 ，那么 parent*2+1 = 1*2+1 = 3
且 2 节点的左孩子是 7，在数组中 7 元素的下标就是 3
所以想要得到当前节点的左孩子的下标，就通过 parent*2+1 的公式就能得到

先找出左右孩子节点中大的那个孩子节点，再和当前父亲节点作比较
如果比父亲节点大的话，那么就交换，再迭代，继续往下找，直到 child 不满足小于 size 或者不大于父亲节点时就停止交换

注意：向下调整建堆的前提是父亲节点的左右子树已经是大/小堆，否则无论如何向下调整，数组都不能建成堆

---

堆排序算法的实现（默认升序）

代码演示：

void HeapSort(int* a, int size)
{// 建大堆for (int i = (size - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, size, i);}// 排升序for (int i = size - 1; i > 0; i--){// 首尾交换Swap(&a[0], &a[i]);// 向下调整AdjustDown(a, i, 0);}
}

代码解析：

如何利用向下调整算法对数组建堆的理论已经在前言里面的博客中写到过，这里就不过多赘述了

建大堆的原因是：大堆的特点是最大的元素在数组首元素的位置，那么就把首尾交换，最大的元素就到了数组尾元素的位置
再通过向下调整算法向下调整，保证数组还是一个堆，并且最后一个元素就不要动了，所以通过 i 来控制向下调整算法中的 size 数组个数，直到不满足 i > 0 时，此时的数组就是升序了

代码验证：