堆排序是是一种利用堆这种数据结构进行排序的算法。它先把数组变成一个大顶堆或小顶堆然后反复取出堆顶最大/最小值放到末尾再重新调整剩余部分直到全部有序。今天就结合我自己写的完整代码一步步拆解堆排序的核心逻辑从函数实现到难点解析新手也能轻松看懂、上手使用。//堆排序 时间复杂度 O(nlogn) 空间复杂度 O(1) 稳定性不稳定 //堆排序的核心函数单次调整函数 //start end 表示要调整的框框的开始节点小标和结束节点下标 void HeapAdjust(int arr[], int start, int end) { int tmp arr[start]; int i start * 2 1; while (i end) { if (i 1 end arr[i] arr[i 1]) { i; } if (arr[i] tmp) { arr[start] arr[i]; start i; i 2 * i 1; } else { break; } } arr[start] tmp; } void HeapSort(int arr[], int len) { //1.由内到外的调整 for (int i (len - 1 - 1) / 2; i 0; i--) { HeapAdjust(arr, i, len - 1); //难点1 } //2.头尾交换断开尾节点连接然后再重新调整为大顶堆 /*for (int i 0; i len - 1; i)*/ for (int i len - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; HeapAdjust(arr, 0, i - 1); } }一、堆排序的本质堆排序的本质是“利用堆的特性大顶堆/小顶堆进行排序”核心分为两步这两步对应上面的两个函数缺一不可构建初始大顶堆把无序数组转换成大顶堆父节点的值 ≥ 左右子节点的值这一步靠 HeapSort 函数中的第一个循环实现依赖 HeapAdjust 辅助。交换调整堆把堆顶数组第一个元素也是当前堆的最大值和堆的末尾元素交换然后把末尾元素“断开”不再参与堆调整再重新调整剩余元素为大顶堆重复此过程直到所有元素有序。这里我用的是「大顶堆」实现升序排序逻辑更直观也是最常用的写法。二、函数拆解HeapAdjust这是堆排序的“灵魂函数”很多人看不懂堆排序本质是没搞懂这个函数的作用。先明确它的功能作用给定一个数组指定调整范围start 到 end把 start 位置作为根节点的子树调整成大顶堆。简单说就是让 start 位置的节点“下沉”到它应该在的位置保证子树满足大顶堆规则。void HeapAdjust(int arr[], int start, int end) { int tmp arr[start]; // 1. 保存根节点待下沉的节点防止后续覆盖丢失 nt i start * 2 1; // 2. i 指向 start 的左孩子数组下标从0开始左孩子公式父节点*21 while (i end) // 3. 循环条件左孩子在调整范围内没超出堆的边界 { // 4. 找到左右孩子中更大的那个如果右孩子存在且比左孩子大就选右孩子 if (i 1 end arr[i] arr[i 1]) { i; // i 切换到右孩子 } // 5. 如果孩子比根节点tmp大说明根节点需要下沉 if (arr[i] tmp) { arr[start] arr[i]; // 孩子上浮覆盖父节点 start i; // 根节点位置更新为当前孩子的位置继续向下检查 2 * i 1; // 找到新根节点的左孩子继续循环下沉 } else { break; // 6. 如果孩子不比根节点大说明已经是大顶堆退出循环 } } arr[start] tmp; // 7. 把最初保存的根节点放到它最终的位置下沉后的位置 }关键细节补充为什么要先保存根节点 tmp因为后续会用孩子节点的值覆盖父节点arr[start] arr[i]如果不保存根节点的值会丢失最后无法放到正确位置。循环的终止条件有两个要么 i 超出 end没有孩子了要么孩子节点不比 tmp 大已经满足大顶堆。三、主函数拆解HeapSort堆排序主逻辑这个函数负责串联“建堆”和“排序”两个核心步骤代码不长但有一个高频面试难点我们逐部分拆解。第一步构建初始大顶堆难点重点//1.由内到外的调整构建初始大顶堆 for (int i (len - 1 - 1) / 2; i 0; i--) { HeapAdjust(arr, i, len - 1); //难点1 }这里的核心难点为什么 i 要从 (len-1-1)/2 开始并且从后往前遍历先解释公式(len-1-1)/2 是「最后一个非叶子节点的下标」。数组最后一个元素的下标是 len-1它的父节点就是 (len-1 - 1)/2父节点下标 (子节点下标 - 1)/2。非叶子节点有孩子的节点叶子节点不需要调整没有孩子本身就是大顶堆。为什么从后往前因为如果从前往后调整后面的非叶子节点调整后会打乱前面已经调整好的子树导致建堆失败从后往前能保证每一个子树调整好后不会被后续操作打乱最终整个数组变成大顶堆。第二步交换调整完成排序//2.头尾交换断开尾节点连接然后再重新调整为大顶堆 for (int i len - 1; i 0; i--) { // 交换堆顶最大值和当前堆末尾元素 int tmp arr[0]; arr[0] arr[i]; rr[i] tmp; // 重新调整剩余元素为大顶堆排除已经排好序的末尾元素 eapAdjust(arr, 0, i - 1); }这一步的逻辑很简单我们拆解成3步交换堆顶arr[0]是当前堆的最大值和堆末尾元素arr[i]交换这样最大值就放到了它最终的有序位置数组末尾。断开i 从 len-1 开始每次循环 i--意味着“已排序的末尾元素”不再参与后续堆调整调整范围变成 0 到 i-1。调整交换后堆顶元素变成了原来的末尾元素大概率不满足大顶堆规则所以调用 HeapAdjust 函数只调整 0 到 i-1 的范围把剩余元素重新变成大顶堆为下一次交换做准备。循环直到 i0此时所有元素都已排序完成。四、堆排序关键属性面试必背结合代码和逻辑整理出面试高频考点时间复杂度O(nlogn)。建堆的时间复杂度是 O(n)后续 n-1 次调整每次调整的时间复杂度是 O(logn)整体就是 O(n nlogn) O(nlogn)。空间复杂度O(1)。全程没有开辟额外的数组只用到了几个临时变量tmp、i、start属于原地排序。稳定性不稳定。排序过程中相同值的元素可能会因交换被打乱原始顺序比如 [2, 2, 1]排序后两个 2 的位置可能颠倒。五、运行与总结加上打印数组与测试程序// 打印数组 void PrintArray(int arr[], int len) { for (int i 0; i len; i) { printf(%d , arr[i]); } printf(\n); } int main() { // 测试用例 int arr[] {4, 6, 8, 5, 9, 1, 3, 2, 7}; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); PrintArray(arr, len); // 调用堆排序函数 eapSort(arr, len); printf(排序后); PrintArray(arr, len); return 0; }运行后就会得到如下结果排序前4 6 8 5 9 1 3 2 7排序后1 2 3 4 5 6 7 8 9堆排序的优势的是「高效原地排序」在数据量较大的场景下表现优异也是面试中常考的 O(nlogn) 排序算法之一。掌握它的关键就是理解 HeapAdjust 函数的“节点下沉”逻辑以及建堆时“从最后一个非叶子节点从后往前遍历”的原因。