堆排序

堆排序是一种高效、基于比较的排序算法。它利用一种称为“二叉堆”的数据结构，通过将其输入分成已排序和未排序区域，并通过提取最大元素并将其移动到已排序区域来迭代地缩小未排序区域。它是一种原地算法，但不是稳定的排序。它涉及构建一个最大堆，这是一个基于树的特殊数据结构，然后将根节点（最大元素）与最后一个节点交换，堆的大小减一，并对根节点进行堆化。现在最大元素位于列表的末尾，这个步骤会重复进行，直到所有节点都排序完成。堆排序提供了一种良好的最坏情况运行时间 O(n log n)，无论输入数据如何。