堆排序
最后更新
堆排序把数组看作一个二叉堆。它先建立最大堆，让最大的元素位于根节点（索引 0）。然后反复把根节点与最后一个未排序元素交换，把最大值固定到位，再把新的根节点下沉（sift down），恢复堆的性质。点击上方的“播放”，观看建堆和逐个取出最大值的过程。
堆排序和归并排序一样保证 O(n log n) 的时间复杂度，但它是原地排序，只需要 O(1) 的额外空间。它不稳定，缓存表现通常也比快速排序差，所以多在既需要有保证的时间上界、又要求常数级内存时选用。
时间复杂度与空间复杂度
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 建堆 + n 次取出 |
| 平均情况 | O(n log n) | 随机顺序 |
| 最坏情况 | O(n log n) | 有保证 |
| 空间 | O(1) | 原地排序 |
| 稳定性 | 不稳定 | 下沉操作会打乱相等元素的顺序 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 用数组建立最大堆（从最后一个父节点开始向前逐个下沉）。 |
| 2 | 把根节点（最大值）与堆中的最后一个元素交换。 |
| 3 | 把堆的大小减一，最后这个位置就排好了。 |
| 4 | 让新的根节点下沉，恢复最大堆的性质。 |
| 5 | 重复以上步骤，直到堆中只剩一个元素。 |
实例演示
对 [3, 1, 6, 5, 2, 4] 排序。竖线 | 标出不断缩小的堆和已排序尾部之间的分界：
| 轮次 | 数组 | 操作 |
|---|---|---|
| 建堆 | [6, 5, 4, 1, 2, 3] | 从最后一个父节点开始下沉，建立最大堆；6 现在位于根节点。 |
| 1 | [5, 3, 4, 1, 2 | 6] | 把根节点 6 与最后一个位置交换，缩小堆，再让 3 下沉。 |
| 2 | [4, 3, 2, 1 | 5, 6] | 把根节点 5 换出去，再让 2 下沉，4 升到根节点。 |
| 3 | [3, 1, 2 | 4, 5, 6] | 把根节点 4 换出去，再让 1 下沉，3 升到根节点。 |
| 4 | [2, 1 | 3, 4, 5, 6] | 把根节点 3 换出去；2 已经满足堆的性质。 |
| 5 | [1 | 2, 3, 4, 5, 6] | 把根节点 2 换出去；只剩一个元素，数组排序完成。 |
什么时候用堆排序
| 适合使用 | 不适合使用 |
|---|---|
你需要有保证的 O(n log n) 最坏情况，完全不想冒 O(n²) 的风险。 | 你需要稳定排序，保留相等键的原有顺序。 |
内存紧张：它是原地排序，只需要 O(1) 的额外空间。 | 看重缓存性能且数据能放进内存：这时快速排序通常更快。 |
| 你本来就在数据上维护一个堆（例如优先队列）。 | 你想让比较次数最少：实际中归并排序和快速排序的比较往往更少。 |
| 不可信的输入可能触发快速排序的最坏情况，而你又无法随机化。 | 数据几乎有序：插入排序在这种数据上接近线性时间。 |
Heap Sort 代码
简洁、可运行的 Heap Sort 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Heap Sort 的 Python 代码
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Heap Sort 的 JavaScript 代码
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Heap Sort 的 Java 代码
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Heap Sort 的 C++ 代码
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Heap Sort 的 C 代码
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}堆排序常见问题
堆排序的时间复杂度是多少？
堆排序在最好、平均和最坏情况下都是
O(n log n)。建堆需要 O(n)，n 次取出每次花费 O(log n)。它只用 O(1) 的额外空间。堆排序是稳定的吗？
不是。下沉操作可能让相等的元素互相越过，所以堆排序不能保留相等键的相对顺序。
什么时候应该用堆排序？
当你需要有保证的
O(n log n) 最坏情况，同时只能用 O(1) 额外内存时，就用堆排序。它避开了快速排序 O(n²) 的风险，也不需要归并排序 O(n) 的缓冲区，代价是不稳定、缓存性能较差。堆排序和快速排序有什么区别？
两者都是原地排序，但快速排序的最坏情况是
O(n²)，而堆排序保证 O(n log n)。实际中快速排序通常更快，因为它的缓存局部性更好、交换次数更少，所以堆排序主要用在必须保证最坏情况上界的场合。堆排序和优先队列有什么关系？
二叉堆是优先队列的标准实现，而堆排序本质上就是不断从这个队列中弹出最大值。如果你的数据本来就存放在堆里，逐个取出元素就能直接得到有序结果。
堆排序要用最大堆还是最小堆？
要原地升序排序，就用最大堆：每一轮把最大的元素换到末尾，已排序部分从右边逐渐变长。用最小堆原地排序会得到降序结果；如果把元素取出到另一个数组里，则得到升序结果。
相关资源
更多可视化
