排序算法完全指南（七）：堆排序深度详解

引言前面我们学习了插入排序的升级版——希尔排序。今天要讲的堆排序是另一种 O(n log n) 级别的排序算法而且它是原地排序不需要像归并排序那样额外开辟数组空间。堆排序的核心是堆这个数据结构——一种特殊的完全二叉树。它利用堆的堆顶一定是最大或最小值这个特性反复取出堆顶元素放到数组末尾最终完成排序。第一部分堆的基本概念一、什么是堆堆是一棵完全二叉树且满足堆序性质大顶堆每个节点的值都 ≥ 其子节点的值堆顶最大小顶堆每个节点的值都 ≤ 其子节点的值堆顶最小二、堆的数组存储完全二叉树可以用数组高效存储节点下标 i左子 (2i1)右子 (2i2)父节点 ((i-1)/2)50012—451340402560203781107——3最后一个非叶子节点的下标(len - 1 - 1) / 2 (len - 2) / 2这个公式很重要因为建堆时要从最后一个非叶子节点开始向前调整。第二部分算法核心——向下调整一、向下调整的原理HeapAdjust(arr, start, end)的作用是把以 start 为根的子树调整成大顶堆。前提start 的左右子树已经是大顶堆。二、向下调整代码// 把以 start 为根的子树调整成大顶堆 // end堆的边界数组下标不包含 end1 及之后 void HeapAdjust(int arr[], int start, int end) { int tmp arr[start]; // 保存根节点值 int maxchild start * 2 1; // 左子下标 while (maxchild end) { // 找左右子中更大的那个 if (maxchild 1 end arr[maxchild 1] arr[maxchild]) { maxchild; // 右子更大 } // 如果最大的子节点 tmp子节点上浮 if (arr[maxchild] tmp) { arr[start] arr[maxchild]; start maxchild; // 继续向下检查 maxchild start * 2 1; } else { break; // 位置正确停止 } } arr[start] tmp; // tmp 最终落位 }代码要点变量含义tmp保存要调整的根节点值maxchild当前检查位置的左子下标start当前检查的位置会变化end堆的边界不能越界第三部分堆排序完整实现一、建堆// 从最后一个非叶子节点开始向前逐个调整 for (int i (len - 1 - 1) / 2; i 0; i--) { HeapAdjust(arr, i, len - 1); }为什么从(len-2)/2开始二、排序过程void Heap_Sort(int arr[], int len) { // 第一步建堆 for (int i (len - 2) / 2; i 0; i--) { HeapAdjust(arr, i, len - 1); } // 第二步反复交换 调整 for (int j 0; j len - 1; j) { // 堆顶最大值与当前堆末尾交换 int tmp arr[0]; arr[0] arr[len - 1 - j]; arr[len - 1 - j] tmp; // 交换后堆的范围缩小重新调整 HeapAdjust(arr, 0, len - 1 - 1 - j); } }三、完整排序过程图解第四部分完整测试代码#include stdio.h void HeapAdjust(int arr[], int start, int end) { int tmp arr[start]; int maxchild start * 2 1; while (maxchild end) { if (maxchild 1 end arr[maxchild 1] arr[maxchild]) { maxchild; } if (arr[maxchild] tmp) { arr[start] arr[maxchild]; start maxchild; maxchild start * 2 1; } else { break; } } arr[start] tmp; } void Heap_Sort(int arr[], int len) { // 建堆 for (int i (len - 2) / 2; i 0; i--) { HeapAdjust(arr, i, len - 1); } // 交换 调整 for (int j 0; j len - 1; j) { int tmp arr[0]; arr[0] arr[len - 1 - j]; arr[len - 1 - j] tmp; HeapAdjust(arr, 0, len - 2 - j); } } void printArray(int arr[], int len, const char* msg) { printf(%s, msg); for (int i 0; i len; i) printf(%d , arr[i]); printf(\n); } int main() { int arr1[] {35, 45, 40, 20, 25, 50, 30, 10, 15}; int len1 sizeof(arr1) / sizeof(arr1[0]); printArray(arr1, len1, 排序前); Heap_Sort(arr1, len1); printArray(arr1, len1, 排序后); int arr2[] {8, 7, 6, 5, 4, 3, 2, 1}; int len2 sizeof(arr2) / sizeof(arr2[0]); printf(\n逆序测试\n); printArray(arr2, len2, 排序前); Heap_Sort(arr2, len2); printArray(arr2, len2, 排序后); int arr3[] {1, 2, 3, 4, 5, 6, 7, 8}; int len3 sizeof(arr3) / sizeof(arr3[0]); printf(\n已有序测试\n); printArray(arr3, len3, 排序前); Heap_Sort(arr3, len3); printArray(arr3, len3, 排序后); return 0; }第五部分算法分析一、时间复杂度阶段复杂度推导建堆O(n)看似 O(n log n)实际是 O(n)每次调整O(log n)沿着树的高度比较排序O(n log n)n-1 次交换每次调整 O(log n)总计O(n log n)建堆为什么是 O(n)二、空间复杂度O(1)只用了临时变量tmp和maxchild。三、稳定性堆排序是不稳定的。因为堆顶和末尾交换是跳跃式的可能破坏相等元素的相对顺序。第六部分堆排序 vs 其他 O(n log n) 排序对比项快速排序归并排序堆排序平均时间O(n log n)O(n log n)O(n log n)最坏时间O(n²)O(n log n)O(n log n)空间O(log n)O(n)O(1)稳定性❌✅❌缓存友好✅ 最好一般❌ 最差堆排序的特点✅ 最坏也是 O(n log n)没有退化问题✅ 原地排序空间 O(1)❌ 不稳定❌ 跳跃访问缓存不友好实际速度通常不如快排总结一、核心要点要点内容数据结构堆 完全二叉树 堆序性质父/子下标左子 2i1右子 2i2父 (i-1)/2建堆从(len-2)/2开始向前调整O(n)排序交换 调整共 n-1 轮O(n log n)总复杂度O(n log n)空间 O(1)稳定性❌ 不稳定二、代码框架记忆三、一句话记忆堆排序用完全二叉树的数组存储实现建堆 O(n)反复取堆顶最大值放到末尾 O(n log n)是唯一能做到原地 O(n log n) 最坏的排序算法。