堆排序 (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、2564 最大无需交换。建堆完成堆顶 64 为全局最大值。当前数组[64, 34, 25, 12, 22]第 2 轮选出最大值 64目标将堆顶 64 与末尾元素 22 交换并对前 4 个元素重新堆化。交换 64 和 22数组变为[22, 34, 25, 12, | 64]对 22 进行向下调整22 的左孩子是 34右孩子是 2534 最大交换 22 和 34。第 2 轮结束最大值 64 归位。当前数组[34, 22, 25, 12, | 64]第 3 轮选出第二大值 34目标将堆顶 34 与倒数第二个元素 12 交换并对前 3 个元素重新堆化。交换 34 和 12数组变为[12, 22, 25, | 34, 64]对 12 进行向下调整12 的孩子是 22 和 2525 最大交换 12 和 25。第 3 轮结束第二大值 34 归位。当前数组[25, 22, 12, | 34, 64]第 4 轮选出第三大值 25目标将堆顶 25 与倒数第三个元素 12 交换并对前 2 个元素重新堆化。交换 25 和 12数组变为[12, 22, | 25, 34, 64]对 12 进行向下调整12 的左孩子是 2222 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)\)(原地排序仅需常数级的额外空间用于交换变量)