第10课：堆排序
进度 0/24
🏃
堆排序
一边建堆一边出队，排序自然完成！
📖知识引入
🏗️建堆
从n/2号节点倒着到1号逐个下沉，O(n)就能建好大根堆
🎯排序思路
堆顶最大与末尾交换，堆规模减一，再把新堆顶下沉
📈O(n log n)
每次取最值花O(log n)，取n次，稳定的高效排序
🏠原地排序
不需要额外数组，只在原数组里交换，省下宝贵内存
💡
建堆从n/2倒着来，因为下标大于n/2的节点全是叶子，天然不用下沉
🔍完整的堆排序
void sink(int h[], int n, int i) { // 让 h[i] 下沉到位
while (2 * i <= n) {
int son = 2 * i;
if (son + 1 <= n && h[son + 1] > h[son]) son++;
if (h[i] >= h[son]) break;
swap(h[i], h[son]);
i = son;
}
}
void heapSort(int a[], int n) {
for (int i = n / 2; i >= 1; i--) sink(a, n, i); // O(n) 建堆
for (int i = n; i > 1; i--) {
swap(a[1], a[i]); // 当前最大值放到末尾
sink(a, i - 1, 1); // 剩余部分重新下沉
}
}先建大根堆，再反复交换堆顶与末尾并下沉。
🎯小测验
第1题：堆排序的总时间复杂度是？
第2题：建堆时从哪个下标开始下沉？
第3题：用大根堆堆排序，最终数组是？
📝本课知识点
- ✓建堆从n/2倒着来
- ✓堆顶换末尾再下沉
- ✓堆排序O(n log n)
第10课完成！继续探索下一课吧 🚀