困难排序 · 堆排
堆排序 图解题解
这道题到底在问什么
给定一个整数数组 nums，把它原地升序排好。堆排序的做法：先建大顶堆，再反复「堆顶换到末尾 + 下沉修复」。
- 输入
- nums = [4,1,3,2,6,5]
- 输出
- [1,2,3,4,5,6]
最优解：一步一步想明白
- 3记住一句话：下沉(sift down) = 父亲若比孩子小，就和较大的孩子换位置，一路往下，直到坐稳。建堆和取顶后修复，用的都是这一个动作。
- 4取顶 = 堆顶换到末尾(最大值归位) → 堆缩小一格 → 新堆顶下沉修复。每轮锁定一个最大值在尾部，绿色就是已排好的部分。
- 5第一阶段：建大顶堆。从最后一个「有孩子的节点」开始，逐个向前做下沉，把每棵子树都整理成父亲最大。
- 6处理子树根 下标 2：看父亲(橙)下标 2=3 和它的孩子下标 5=5：较大的孩子是下标 5=5，父亲更小，需要交换。
- 7交换：父亲和较大的孩子换位，现在下标 2 处坐着更大的 5。被换下去的 3 继续往下沉，看它还压不压得住孙辈。
- 8处理子树根 下标 2：看父亲(橙)下标 5=3 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 9处理子树根 下标 1：看父亲(橙)下标 1=1 和它的孩子下标 3=2、下标 4=6：较大的孩子是下标 4=6，父亲更小，需要交换。
- 10交换：父亲和较大的孩子换位，现在下标 1 处坐着更大的 6。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
- 11处理子树根 下标 1：看父亲(橙)下标 4=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 12处理子树根 下标 0：看父亲(橙)下标 0=4 和它的孩子下标 1=6、下标 2=5：较大的孩子是下标 1=6，父亲更小，需要交换。
- 13交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 6。被换下去的 4 继续往下沉，看它还压不压得住孙辈。
- 14处理子树根 下标 0：看父亲(橙)下标 1=4 和它的孩子下标 3=2、下标 4=1：父亲已经是其中最大，不用动，下沉结束。
- 15大顶堆建好了：堆顶下标 0=6 就是整个数组的最大值。接下来进入取顶阶段，把它换到末尾归位。
- 16取顶第 1 轮：把堆顶 6(当前最大)和堆的最后一格 下标 5=3 交换，最大值即将归位到尾部。
- 17最大值 6 归位到下标 5，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…4。
- 18新堆顶下沉：看父亲(橙)下标 0=3 和它的孩子下标 1=4、下标 2=5：较大的孩子是下标 2=5，父亲更小，需要交换。
- 19交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 5。被换下去的 3 继续往下沉，看它还压不压得住孙辈。
- 20新堆顶下沉：看父亲(橙)下标 2=3 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 21取顶第 2 轮：把堆顶 5(当前最大)和堆的最后一格 下标 4=1 交换，最大值即将归位到尾部。
- 22最大值 5 归位到下标 4，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…3。
- 23新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=4、下标 2=3：较大的孩子是下标 1=4，父亲更小，需要交换。
- 24交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 4。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
- 25新堆顶下沉：看父亲(橙)下标 1=1 和它的孩子下标 3=2：较大的孩子是下标 3=2，父亲更小，需要交换。
- 26交换：父亲和较大的孩子换位，现在下标 1 处坐着更大的 2。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
- 27新堆顶下沉：看父亲(橙)下标 3=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 28取顶第 3 轮：把堆顶 4(当前最大)和堆的最后一格 下标 3=1 交换，最大值即将归位到尾部。
- 29最大值 4 归位到下标 3，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…2。
- 30新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=2、下标 2=3：较大的孩子是下标 2=3，父亲更小，需要交换。
- 31交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 3。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
- 32新堆顶下沉：看父亲(橙)下标 2=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 33取顶第 4 轮：把堆顶 3(当前最大)和堆的最后一格 下标 2=1 交换，最大值即将归位到尾部。
- 34最大值 3 归位到下标 2，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…1。
- 35新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=2：较大的孩子是下标 1=2，父亲更小，需要交换。
- 36交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 2。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
- 37新堆顶下沉：看父亲(橙)下标 1=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
- 38取顶第 5 轮：把堆顶 2(当前最大)和堆的最后一格 下标 1=1 交换，最大值即将归位到尾部。
- 39最大值 2 归位到下标 1，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…0。
- 40堆里只剩下标 0 一个元素，它自然就是最小值，留在最前面。整个数组已经从小到大排好。
⚠️ 容易写错的地方
✗ 错：下沉时只和左孩子比，忘了挑「较大的那个孩子」
✓ 对：先在左右孩子里选大的，再拿父亲和它比
和较小的孩子换会破坏大顶堆性质：换上去的仍可能比另一个孩子小
✗ 错：建堆从下标 0 往后正序下沉
✓ 对：从最后一个父节点 n//2-1 倒着往前下沉
下沉依赖「孩子子树已经是堆」，必须自底向上；正序做底层还没整理，会漏
✗ 错：取顶后忘了缩小堆范围，对已归位元素继续下沉
✓ 对：每取一次顶就把上界 end 减一，归位的不再参与
不缩小范围会把已排好的最大值又卷回堆里，破坏结果
完整代码（Python / C++ / Java）
Python
def heap_sort(nums):
n = len(nums)
def sift_down(i, end): # 下沉：父若小于较大孩子则换
while 2*i+1 <= end:
big = 2*i+1
if big+1 <= end and nums[big+1] > nums[big]:
big += 1
if nums[i] >= nums[big]: break
nums[i], nums[big] = nums[big], nums[i]
i = big
for p in range(n//2-1, -1, -1): # 建大顶堆
sift_down(p, n-1)
for end in range(n-1, 0, -1): # 反复取顶
nums[0], nums[end] = nums[end], nums[0]
sift_down(0, end-1)
return numsC++
void siftDown(vector<int>& a, int i, int end){
while (2*i+1 <= end) {
int big = 2*i+1;
if (big+1 <= end && a[big+1] > a[big]) big++;
if (a[i] >= a[big]) break;
swap(a[i], a[big]); i = big;
}
}
void heapSort(vector<int>& a){
int n = a.size();
for (int p = n/2-1; p >= 0; p--) siftDown(a, p, n-1);
for (int end = n-1; end > 0; end--) {
swap(a[0], a[end]); siftDown(a, 0, end-1);
}
}Java
void siftDown(int[] a, int i, int end){
while (2*i+1 <= end) {
int big = 2*i+1;
if (big+1 <= end && a[big+1] > a[big]) big++;
if (a[i] >= a[big]) break;
int t=a[i]; a[i]=a[big]; a[big]=t; i = big;
}
}
void heapSort(int[] a){
int n = a.length;
for (int p = n/2-1; p >= 0; p--) siftDown(a, p, n-1);
for (int end = n-1; end > 0; end--) {
int t=a[0]; a[0]=a[end]; a[end]=t; siftDown(a, 0, end-1);
}
}复杂度
时间
O(n log n)
建堆 O(n)；之后取顶 n-1 次，每次下沉 O(log n)，合计 O(n log n)
空间
O(1)
原地交换，只用常数个临时变量，不开额外数组（迭代版下沉无递归栈）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 堆排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
堆排序是稳定排序吗？+
不是。下沉过程中相等的元素会因为交换改变相对顺序，所以堆排序不稳定。需要稳定时一般用归并排序。
建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)？+
虽然有 n/2 个父节点要下沉，但越靠近底层的节点越多、能下沉的高度越小。把每层节点数 × 该层最大下沉高度求和，是一个收敛级数，结果是 O(n)。
堆排序和快速排序怎么选？+
快排平均更快、常数小，但最坏 O(n²)；堆排序最坏也稳定在 O(n log n) 且原地，适合对最坏情况有要求的场景。两者都不稳定。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 堆排序 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。