堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
假设有一个待排序的列表 [4, 10, 3, 5, 1]，堆排序的过程如下：
构建最大堆：
初始列表：[4, 10, 3, 5, 1]。
从最后一个非叶子节点开始，逐步调整堆：
调整节点 5：[4, 10, 3, 5, 1]（无需调整）。
调整节点 10：[4, 10, 3, 5, 1]（无需调整）。
调整节点 4：[10, 5, 3, 4, 1]。
最终最大堆：[10, 5, 3, 4, 1]。
交换堆顶元素：
将堆顶元素 10 与最后一个元素 1 交换，列表变为 [1, 5, 3, 4, 10]。
堆的大小减 1，已排序部分为 [10]。
调整堆：
对新的堆顶元素 1 进行下沉操作：
比较 1 和其子节点 5、3，将 1 与 5 交换。
列表变为 [5, 1, 3, 4, 10]。
继续比较 1 和其子节点 4，将 1 与 4 交换。
列表变为 [5, 4, 3, 1, 10]。
调整后的堆：[5, 4, 3, 1]。
重复步骤：
将堆顶元素 5 与最后一个元素 1 交换，列表变为 [1, 4, 3, 5, 10]。
堆的大小减 1，已排序部分为 [5, 10]。
对新的堆顶元素 1 进行下沉操作：
比较 1 和其子节点 4、3，将 1 与 4 交换。
列表变为 [4, 1, 3, 5, 10]。
调整后的堆：[4, 1, 3]。
继续重复：
将堆顶元素 4 与最后一个元素 3 交换，列表变为 [3, 1, 4, 5, 10]。
堆的大小减 1，已排序部分为 [4, 5, 10]。
对新的堆顶元素 3 进行下沉操作：
比较 3 和其子节点 1，无需交换。
调整后的堆：[3, 1]。
最终步骤：
将堆顶元素 3 与最后一个元素 1 交换，列表变为 [1, 3, 4, 5, 10]。
堆的大小减 1，已排序部分为 [3, 4, 5, 10]。
堆的大小为 1，排序完成。
构建最大堆：O(n)。
每次调整堆：O(log n)，总共需要调整 n-1 次。
O(1)，堆排序是原地排序算法，不需要额外的存储空间。
优点：
原地排序，不需要额外的存储空间。
缺点：
不稳定排序算法（可能改变相同元素的相对顺序）。
对于小规模数据，性能可能不如插入排序等简单算法。
大规模数据集的排序。
对性能要求较高的场景。
适合内存排序（不适合外部排序）。
艾孜尔江
上方又没些 C# 的堆排序，艾孜尔江补充如下：
艾孜尔江
大兵小将
堆排序是不稳定的排序！
既然如此，每次构建大顶堆时，在 父节点、左子节点、右子节点取三者中最大者作为父节点就行。我们追寻的只是最终排序后的结果，所以可以简化其中的步骤。
我将个人写的 Java 代码核心放在下方，有兴趣的同学可以一起讨论下：