堆排序
入门原地 O(n log n) 排序，理解堆的构建与下沉操作。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void heapify(int arr[], int n, int i) {
2 int largest = i;
3 int left = 2 * i + 1;
4 int right = 2 * i + 2;
5
6 if (left < n && arr[left] > arr[largest]) largest = left;
7 if (right < n && arr[right] > arr[largest]) largest = right;
8
9 if (largest != i) {
10 swap(arr[i], arr[largest]);
11 heapify(arr, n, largest);
12 }
13}
14
15void heapSort(int arr[], int n) {
16 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
17 for (int i = n - 1; i > 0; i--) {
18 swap(arr[0], arr[i]);
19 heapify(arr, i, 0);
20 }
21}
复杂度分析
时间 O(n log n)
空间 O(1)
最优 O(n log n)
最坏 O(n log n)
算法讲解
堆排序首先将数组构建为最大堆，此时 arr[0] 是全局最大值。
将堆顶与末尾元素交换，缩小堆的范围，再对新的堆顶执行下沉（heapify）。
重复 n-1 次后，数组变为升序。
时间复杂度 O(n log n)，空间复杂度 O(1)，但不稳定。