【算法精解】堆排序（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)$。