【算法精解】堆排序（Heap Sort）原理、实现与深度解析（C++版）
1. 引言
在众多的O(n \log n)排序算法中，堆排序（Heap Sort）以其不需要额外辅助空间（原地排序）和稳定的最坏时间复杂度而著称。它巧妙地利用了“完全二叉树”的逻辑结构来管理数组元素。
2. 堆排序的核心思想
堆排序主要分为两个阶段：
建堆（Build Heap）：将一个无序序列调整为一个大顶堆（或小顶堆）。
排序（Sort Iteration）：不断将堆顶元素（当前最大值）交换到数组末尾，并重新调整堆。
3. 代码实现
以下是基于 C++ 的堆排序实现，包含详细的注释说明：
C++
#include <iostream> #include <cstdlib> #include <ctime> using namespace std; /** * 堆的下沉调整（siftDown） * @param arr 待调整数组 * @param i 当前需要下沉的节点索引 * @param size 当前有效堆的大小 */ void siftDown(int arr[], int i, int size) { int val = arr[i]; // 暂存当前节点值 while (2 * i + 1 < size) { // 只要有左孩子，就尝试下沉 int child = 2 * i + 1; // 左孩子索引 // 如果有右孩子，且右孩子的值比左孩子大，则选择右孩子 if (child + 1 < size && arr[child + 1] > arr[child]) { child++; } // 如果孩子节点比父亲节点大，则将孩子上移 if (arr[child] > val) { arr[i] = arr[child]; i = child; // 更新索引，继续向下比较 } else { break; // 满足大顶堆性质，跳出 } } arr[i] = val; // 将最初的节点值放入最终正确位置 } /** * 堆排序主函数 */ void HeapSort(int arr[], int size) { // 阶段一：建堆 // 从最后一个非叶子节点 (size-2)/2 开始向上遍历 for (int i = (size - 2) / 2; i >= 0; i--) { siftDown(arr, i, size); } // 阶段二：排序 // 每次将堆顶（最大值）交换到末尾，并缩小堆范围重新调整 for (int i = size - 1; i > 0; i--) { swap(arr[0], arr[i]); // 交换堆顶和当前末尾 siftDown(arr, 0, i); // 重新对堆顶进行下沉调整，此时堆大小为 i } } int main() { int arr[10]; srand(time(0)); cout << "排序前: "; for (int i = 0; i < 10; i++) { arr[i] = rand() % 100; cout << arr[i] << " "; } cout << endl; HeapSort(arr, 10); cout << "排序后: "; for (int v : arr) { cout << v << " "; } cout << endl; return 0; }4. 关键点深度解析
为什么建堆从 开始？(size - 2) / 2
在完全二叉树的顺序存储中，若索引从 开始：0
最后一个元素的索引是 。
size - 1它的父节点索引是 ，即 。
(i - 1) / 2(size - 1 - 1) / 2 = (size - 2) / 2叶子节点本身已经满足堆的性质，所以我们从最后一个非叶子节点开始调整，效率更高。
复杂度分析
时间复杂度：
建堆：O(n)
排序：O(n \log n)
总体复杂度始终保持在O(n \log n)。
空间复杂度：O(1)，属于原地排序（In-place）。
稳定性：不稳定排序（在交换堆顶和末尾元素时可能会破坏相同元素的相对顺序）。
5. 总结
堆排序在处理海量数据的Top-K 问题时表现非常出色。如果你需要在一个不适合大量内存占用的环境下进行快速排序，堆排序是一个比快速排序更稳健的选择，因为它不会退化到$O(n^2)$。