堆排序 (Heap Sort)
像“选拔赛”一样，每次把数组构造成一个“大顶堆”(保证最顶端是最大值)。然后把冠军(最大值)和队尾的人交换，让他提前“退休”到末尾。接着把剩下的队伍重新调整回大顶堆，再选出新的冠军换到倒数第二个位置。不断重复，队伍就从小到大排好序了。
核心代码
#include <stdio.h> // 堆化函数(向下调整)：维护大顶堆的性质 // n 为当前堆的有效长度，i 为当前需要调整的父节点下标 void heapify(int arr[], int n, int i) { int largest = i; // 假设当前父节点是最大的 int left = 2 * i + 1; // 左孩子下标 int right = 2 * i + 2;// 右孩子下标 // 如果左孩子存在且大于当前最大值，更新最大值下标 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右孩子存在且大于当前最大值，更新最大值下标 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是父节点本身，说明需要交换，并继续向下调整 if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); // 递归调整受影响的子树 } } // 堆排序函数 void heapSort(int arr[], int n) { // 1. 建堆：从最后一个非叶子节点开始，自底向上调整为大顶堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 2. 排序：每次将堆顶(最大值)与末尾元素交换，并缩小堆的范围 for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); // 对剩下的 i 个元素重新堆化 } } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 34, 25, 12, 22}; int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf("排序前："); printArray(arr, n); heapSort(arr, n); // 调用堆排序 printf("排序后："); printArray(arr, n); return 0; }示例演示
{64, 34, 25, 12, 22}
第 1 步：构建初始大顶堆
目标：将无序数组调整为父节点大于等于子节点的大顶堆。
最后一个非叶子节点下标为 5/2 - 1 = 1(元素 34)。比较 34 和它的孩子 12、22，无需交换。
处理下标 0(元素 64)。比较 64 和它的孩子 34、25，64 最大，无需交换。
建堆完成，堆顶 64 为全局最大值。
当前数组：[64, 34, 25, 12, 22]
第 2 轮：选出最大值 64
目标：将堆顶 64 与末尾元素 22 交换，并对前 4 个元素重新堆化。
交换 64 和 22，数组变为：[22, 34, 25, 12, | 64]
对 22 进行向下调整：22 的左孩子是 34，右孩子是 25，34 最大，交换 22 和 34。
第 2 轮结束：最大值 64 归位。
当前数组：[34, 22, 25, 12, | 64]
第 3 轮：选出第二大值 34
目标：将堆顶 34 与倒数第二个元素 12 交换，并对前 3 个元素重新堆化。
交换 34 和 12，数组变为：[12, 22, 25, | 34, 64]
对 12 进行向下调整：12 的孩子是 22 和 25，25 最大，交换 12 和 25。
第 3 轮结束：第二大值 34 归位。
当前数组：[25, 22, 12, | 34, 64]
第 4 轮：选出第三大值 25
目标：将堆顶 25 与倒数第三个元素 12 交换，并对前 2 个元素重新堆化。
交换 25 和 12，数组变为：[12, 22, | 25, 34, 64]
对 12 进行向下调整：12 的左孩子是 22，22 > 12，交换 12 和 22。
第 4 轮结束：第三大值 25 归位。
当前数组：[22, 12, | 25, 34, 64]
第 5 轮：选出第四大值 22
目标：将堆顶 22 与倒数第四个元素 12 交换，堆只剩 1 个元素，无需调整。
交换 22 和 12，数组变为：[12, | 22, 25, 34, 64]
排序完成。
最终结果：[12, 22, 25, 34, 64]
复杂度
时间复杂度是\(O(nlogn)\)(建堆耗时\(O(n)\)，每次调整堆耗时\(O(logn)\)，共调整 n−1 次)
空间复杂度是\(O(1)\)(原地排序，仅需常数级的额外空间用于交换变量)
