【八大经典排序算法】堆排序

---

一、概述

堆排序是J.W.J. Williams于1964年提出的。他提出了一种利用堆的数据结构进行排序的算法，并将其称为堆排序。堆排序是基于选择排序的一种改进，通过维护一个堆来选择最大（或最小）的元素，并将其放置在数组的末尾，然后对剩余的元素进行递归调用堆排序。

堆排序在其初期的版本中存在一些性能问题，例如在构建堆的过程中需要频繁的调整堆的结构，导致性能的下降。为了改进这个问题，人们提出了一种称为“堆调整”的操作，将调整堆的过程优化为一次遍历，从而提高了性能。此外，还有一些其他的改进方法，如使用二叉堆来代替普通堆，使用自底向上的构建堆的方法等。

堆排序作为一种经典的排序算法，经过多年的发展与改进，已经成为一种高效稳定的排序算法，并在实际应用中得到广泛的应用。

---

二、思路解读

我们知道堆排序是一种基于堆数据结构的排序算法，所以堆排序分为以下几步：

①：构建大堆（或小堆）。这里我们从数组的最后一个数据的父节点开始，采用向下调整算法来建堆。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。同时还要注意是调大堆还是小堆。
调小(大)堆：堆顶元素和孩子中最小（大）的节点比较，如果父节点大于（小于）较小的子节点子，两者交换。不断向下调整到合适位置。（调大堆，和较大孩子比较）

②：将堆中最大（或最小）的元素即堆顶元素与数组中最后一个元素交换位置，然后将堆的大小减1。将交换后的堆顶元素进行向下调整，直到堆再次满足堆性质。

③： 重复上述步骤，直到堆的大小为1，此时整个数组就有序了

---

三、代码实现（大堆为例）

void AdjustDown(int* a, int n, int parent)
{//建大堆int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//升序，建大堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

时间复杂度：O(N*logN)
空间复杂度：O(1)