Heap Sort

定义

堆排序（Heap Sort）是利用堆这种数据结构设计的排序算法。堆是一个近似完全二叉树的结构，满足堆的性质：父结点的键值总是大于（大根堆）或小于（小根堆）子结点的键值。

算法步骤

1. 建堆：将无序序列构建成堆（从最后一个非叶子结点开始向下调整）
2. 排序
   • 将堆顶元素（最大/最小值）与末尾元素交换
   • 堆大小减 1，对堆顶元素进行向下调整
   • 重复直到堆大小为 1

时间复杂度

• 建堆：$O(n)$
• 每次调整：$O({\log }_{2}n)$
• 总复杂度：$O(n{\log }_{2}n)$

空间复杂度

$O(1)$，原地排序

稳定性

不稳定

特点

• 最坏、平均、最好情况时间复杂度均为 $O(n{\log }_{2}n)$
• 适合数据量大的场景