目录
在前两篇的文章中，小编主要介绍了关于堆以及堆的代码实现。主要是认识以及了解堆的特性，以
及特别重要得两个调整算法——向上调整算法和向下调整算法。是整个堆实现的关键。在了解了堆
之后，就要掌握堆的应用，也就是今天的内容——堆排序。小编向大家分享一下小编在堆排序这块
的见解。下面我们步入正题：
1.堆排序(HeapSort)
堆排序，顾名思义就是和堆有关的排序，利用堆的性质或者堆的思想对数据进行排序，升序或者降
序。利用堆这种数据结构对数据进行高效排序。小编为了保持文章的完整性和连贯性，在这里对堆
再进行一下简单的介绍，详细介绍可以看前两篇文章。
1.1 堆的基本概念
- 堆：堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。
- 大顶堆：每个节点的值都大于或等于其左右子节点的值，因此堆顶元素是整个堆中的最大值。
- 小顶堆：每个节点的值都小于或等于其左右子节点的值，所以堆顶元素是整个堆中的最小值。
- 完全二叉树：除了最后一层外，其他每一层的节点数都是满的，并且最后一层的节点都靠左排
列。在实际实现中，堆通常使用数组来表示，因为可以通过简单的公式来计算父节点和子节点的位
置。如果父节点的索引为 i ，那么左子节点的索引为 2 * i + 1 ，右子节点的索引为 2 * i + 2 。
1.2 堆排序
1.2.1 版本一(不推荐)
基于已有数组建堆, 取堆顶元素完成排序的版本
这是基于有现成的堆的数据结构的堆排序实现，核心逻辑是借助已有的堆操作(HPPush / HPTop /
HPPop)完成排序，以下是详细拆解：
1. 核心思路:
利用“堆顶是极值（大顶堆/小顶堆）”的特性，先把数组元素全部插入堆，再反复提取堆顶元素，
按顺序覆盖原数组，实现排序。需要注意的是，版本一的堆排序是基于有现成的堆的数据结构的基
础上。也就是说我们首先要有一个关于堆实现的完整代码。也就是小编在上一篇文章中所讲的关于
堆实现的代码。代码很长也较多。为了保持代码的连贯性和逻辑的条理性，下面小编先将完整版的
代码分享给大家：
头文件---Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//堆的结构
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size; //有效数据个数
int capacity; //空间大小
}HP;
//交换函数
void Swap(int* x, int* y);
//向上调整函数
void AdjustUp(HPDataType* arr, int child);
//向下调整函数
void AdjustDown(HPDataType* arr, int parent, int n);
//初始化函数
void HPInit(HP* php);
//销毁函数
void HPDestroy(HP* php);
//打印函数
void HPPrint(HP* php);
//插入函数
void HPPush(HP* php, HPDataType x);
//删除函数
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);
// 判空函数
bool HPEmpty(HP* php);实现文件---Heap.c
#include"Heap.h"
void HPInit(HP* php)
{
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPDestroy(HP* php)
{
if (php->arr)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPPrint(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->arr[i]);
}
printf("\n");
}
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//大堆：>
//小堆：<
if (arr[child] < arr[parent])
{
//调整
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void HPPush(HP* php, HPDataType x)
{
assert(php);
//判断空间是否足够
if (php->size == php->capacity)
{
int newCapcity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapcity*sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapcity;
}
php->arr[php->size] = x;
//向上调整
AdjustUp(php->arr, php->size);
++php->size;
}
// 判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//小堆：>
//大堆：<
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
//小堆: <
//大堆：>
if (arr[child] < arr[parent])
{
//调整
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HPPop(HP* php)
{
assert(!HPEmpty(php));
// 0 php->size-1
Swap(&php->arr[0], &php->arr[php->size - 1]);
--php->size;
//向下调整
AdjustDown(php->arr, 0, php->size);
}
//取堆顶数据
HPDataType HPTop(HP* php)
{
assert(!HPEmpty(php));
return php->arr[0];
}测试文件小编先不给了，这是我们接下来要讲的。下面我们来看版本一堆排序的代码实现。
2. 代码解析:
核心依赖（必须提前实现的堆操作）也就是上面我给的关于堆实现的完整代码中的某些核心函数，
在这里小编再简单强调一下。代码能运行的前提是：已有完整的堆数据结构（ HP 结构体 + 5 个
函数）:
// 堆结构体定义（示例：动态数组实现）
typedef struct {
int* data; // 存储堆元素
int size; // 当前元素个数
int cap; // 容量（可选，动态扩容用）
} HP;
// 1. 堆插入（自动调整结构）
void HPPush(HP* hp, int val) {
// 实现：扩容检查 → 插入数组末尾 → 向上调整堆结构（保证大/小顶堆）
}
// 2. 获取堆顶元素（不删除）
int HPTop(HP* hp) {
return hp->data[0]; // 大顶堆返回最大值，小顶堆返回最小值
}
// 3. 弹出堆顶（自动重建结构）
void HPPop(HP* hp) {
// 实现：首尾交换 → 删除末尾 → 向下调整堆结构（保证剩余元素有序）
}
// 4. 判断堆是否为空
bool HPEmpty(HP* hp) {
return hp->size == 0;
}
// 5. 销毁堆（释放资源）
void HPDestroy(HP* hp) {
free(hp->data); // 释放动态数组
hp->size = hp->cap = 0;
}简单了解了堆数据结构中的几个要使用的核心函数后，我们现在来看关于这个堆排序的代码:
void HeapSort(int* a, int n) // 堆排序函数：a是待排序数组，n是数组长度
{
HP hp; // 定义堆结构体变量（需提前声明：如 typedef struct { ... } HP;）
// 【步骤1：数组元素入堆】
for(int i = 0; i < n; i++)
{
HPPush(&hp,a[i]); // ① 逐个插入元素 → 堆内部自动调整结构（保持大/小顶堆）
}
// 【步骤2：提取堆顶，覆盖原数组】
int i = 0;
while (!HPEmpty(&hp)) // ② 判断堆是否为空 → 非空则继续提取
{
a[i++] = HPTop(&hp); // ③ 堆顶（极值）存入数组 → 利用堆的“有序性”排序
HPPop(&hp); // ④ 弹出堆顶 → 堆自动重建结构（保持大/小顶堆）
}
HPDestroy(&hp); // ⑤ 销毁堆 → 释放内存（避免内存泄漏）
} 核心代码解释:
// 【步骤1：数组元素入堆】
for(int i = 0; i < n; i++)
{
HPPush(&hp,a[i]); // ① 逐个插入元素 → 堆内部自动调整结构（保持大/小顶堆）
}首先这个for循环的逻辑就是通过遍历这个待排序数组，将数组里的数据依次通过堆插入函数插入
到堆内（hp），同时根据堆插入函数里的向上调整函数排 大堆/小堆 。
// 【步骤2：提取堆顶，覆盖原数组】
int i = 0;
while (!HPEmpty(&hp)) // ② 判断堆是否为空 → 非空则继续提取
{
a[i++] = HPTop(&hp); // ③ 堆顶（极值）存入数组 → 利用堆的“有序性”排序
HPPop(&hp); // ④ 弹出堆顶 → 堆自动重建结构（保持大/小顶堆）
}情况一 : 通过前面的for循环，我们已经得到了 大堆/小堆结构 ，以大堆为例 : 如果通过前面的for
循环，堆插入的数据形成的是大堆结构。大堆的堆顶就是最大值。进入while循环内将大堆的堆顶
（极大值）存入新数组中，此时新数组的第一个数 a[0] 就是整个待排序数组中的最大值。显而易
见，此时形成的是降序数组。然后每次通过取堆顶HPTop函数将每次取的极值数字放入新数组并
且通过堆删除HPPop函数( 每次取完一个堆的极值后就删除该极值 ) 里面的向下调整函数使堆仍
然保持大堆结构。直到循环结束，就会得到一个降序数组，从而实现降序。
情况二 : 这是其中一种情况，那如果是小堆呢。我们再来看，以小堆为例：通过前面的for循环，
堆插入函数是待排序数组中的数据形成小堆结构。此时小堆的堆顶就是最小值。进入while循环内
将小堆的堆顶（极小值）存入新数组中。此时新数组中的第一个数 a[0] 就是整个待排序数组中的
最小值。显而易见，此时形成的就是升序数组。和前面我们推导的大堆结构刚好相反。然后通过取
堆顶HPTop函数将每次取得极小值放入新数组中，并且通过堆删除HPPop函数（每次取完一个极
值后就删除该极值）中的向下调整函数使堆仍然保持小堆结构。直到循环结束。就会得到一个升序
数组，从而实现升序。
情况三 : 通过上面两种情况，我们得到了通过大堆结构实现降序和小堆结构实现升序。那么还有没
有其他情况呢？比如说大堆结构实现升序和小堆结构实现降序。答案是有的。这个时候我们只需要
对代码做一个简单的改动。就是将while循环中新数组下标i的起始位置作调整，将 i 的起始位置从
0 改为 n-1 ，这样每次循环取得的极值数字就以从后往前的顺序进行储存。我们再以大堆为例，第
一次取得的堆顶是极大值，将这个极大值放在新数组的最后一个位置，然后依次通过大堆性质将剩
余堆中的最大值按照从后往前的顺序放入新数组中，直到循环结束就会得到一个升序数组。从而通
过大堆结构实现升序。
情况四 : 那么情况四呢，通过小堆结构实现降序，与情况三类似，这个时候每次通过小堆取得的极
值为最小值。依次按照从后往前的顺序存入新数组，直到循环结束就会得到一个降序数组，从而通
过小堆结构实现降序。
下面小编通过表格的方式对这四种情况进行一个总结:
| 排序目标 | 堆类型 | i的起始位置 | 填充方向 | 逻辑原理 |
| 升序 | 小堆 | i = 0 | 从前往后(i++) | 每次取最小值，依次放在数组开头 → 数组从“小→大”排列 |
| 升序 | 大堆 | i = n-1 | 从后往前(i--) | 每次取最大值，依次放在数组末尾 → 数组从“小→大”排列 |
| 降序 | 小堆 | i = n-1 | 从后往前(i--) | 每次取最小值，依次放在数组末尾 → 数组从“大→小”排列 |
| 降序 | 大堆 | i = 0 | 从前往后(i++) | 每次取最大值，依次放在数组开头 → 数组从“大→小”排列 |
仍要注意的是: 版本一堆排序的核心逻辑就是 “堆的类型必须全程一致”，无论插入（ HPPush ）
还是删除（ HPPop ），都要严格维持相同的堆规则（大堆/小堆）。
用一句话总结：
堆排序中，插入和删除的调整逻辑必须配套（同大堆或同小堆），否则堆结构会混乱，排序结果必
然错误。
好了，关于版本一堆排序的主要逻辑，小编已经解释清楚了。还剩最后一个重要的点，那就是复杂
度。
3. 复杂度:
时间复杂度 : O(N log N) (关键：构建堆 + 取堆顶的操作次数）
堆排序的时间复杂度由 “构建堆” 和 “逐个取堆顶” 两部分决定，整体为 O(N log N) （ N 是数组长
度），具体分析：
1. 构建堆（ for 循环 + HPPush ）
- 每次 HPPush 是向堆中插入元素，插入过程需要 向上调整（大堆/小堆规则）。
- 插入第 i 个元素时，调整的时间复杂度是 O(log i) （堆的高度是 log i ，调整需从叶子到根逐层
比较）。
- 总时间： O(log 1 + log 2 + ... + log N) ≈ O(N log N) （对数求和可近似为 N log N 量级）。
2. 取堆顶（ while 循环 + HPTop / HPPop ）
- 每次 HPPop 删除堆顶后，需要 向下调整 修复堆，调整的时间复杂度是 O(log N) （堆的高度是
log N ）。
- 共执行 N 次取堆顶操作（循环 N 次）。
- 总时间： O(N log N) （ N 次操作，每次 O(log N) ）。
3. 整体时间复杂度
构建堆和取堆顶的时间相加：
O(N log N) + O(N log N) = O(N log N)
结论：无论最好、最坏还是平均情况，时间复杂度都是 O(N log N) （堆排序的时间复杂度稳定）
空间复杂度 : O(N) (额外内存占用）
代码中主要的额外空间是 堆结构 HP hp ，用于存储原始数组的元素。
1. 堆的空间占用
- 堆是基于数组构建的，存储 N 个元素，空间复杂度 O(N) 。
2. 其他辅助空间
- 仅用了几个临时变量（如 int i ），空间复杂度可忽略。
3. 整体空间复杂度
额外空间由堆结构主导，因此 空间复杂度是 O(N) 。
4. 总结:
整体可总结为：“借助独立堆结构，用‘先存后取’的逻辑实现排序”，核心特点如下：
1. 核心流程：
先将原数组元素逐个插入独立堆结构（通过 HPPush 建堆，维持大堆/小堆特性），再循环提取堆
顶元素（极值），按顺序覆盖原数组，最终完成排序。
2. 本质特征：
- 依赖额外堆结构存储数据，空间复杂度 O(N) （堆需存一份与原数组等长的数据）。
- 逻辑直观，无需手动处理复杂的数组索引调整，通过堆的封装函数（ HPPush / HPPop ）简化操
作。
3. 排序方向：
由堆类型决定：小堆+前→后填充→升序；大堆+前→后填充→降序。
简言之，这是一种“以空间换简洁”的堆排序实现，核心逻辑清晰，适合理解堆排序的“建堆→取极值
→调整”本质，但内存占用高于原地排序。
到这里，关于版本一堆排序的所有内容已经结束，值得注意的是，该版本有一个前提——必须要有
实现数据结构堆的完整代码。难道我们每次在使用堆排序的时候都要先写数据结构堆的完整代码
吗？这样写不但复杂，而且在空间上会有一定的劣势，也就是空间复杂度较高。下面小编给大家讲
解对排序的第二种方法，也就是版本二。
1.2.2 版本二(推荐)
版本二与版本一不同的原因是 ：版本二直接在待排序的数组上进行操作，无需借助堆结构和其核
心函数，也就是无需开辟多余的空间来表示堆结构。但是：版本二虽然没有借助堆结构来进行排
序，但是其核心思想没有变。仍然是通过堆结构的核心思想进行排序。所以版本二在一定程度上节
省了空间，也叫 原地堆排序。
下面我们来看看代码的实现:
1. 核心思路:
实现原地堆排序:
1. 建堆 : 直接在原数组上构建大堆/小堆（升序建大堆，降序建小堆 ）
2. 排序 : 循环“堆顶与堆尾交换 → 调整堆”，逐步将极值“沉淀”到数组末尾，最终完成排序
2. 代码解析:
原地堆排序是借用了堆结构的核心思想进行排序。即向上调整函数（AdjustUp）和向下调整函数
（AdjustDown）。这两个函数应用于堆中的堆插入函数和堆删除函数中，也是堆的核心函数，下
面小编将这两个函数的代码显示出来，关于这两个函数的解释在上一篇文章有详细说明。
完整版代码:
向上调整函数（AdjustUp）:
void AdjustUp(int* arr, int child)
//参数: int* arr : 待排序数组指针
// int child : 插入元素在数组中的下标
{
int parent = (child - 1) / 2;
while(child > 0)
{
//大堆: >
//小堆: <
if (arr[child] < arr[parent]) //对应上述例子,若 子<父 ,则二者交换位置
{
//调整
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}向下调整函数（AdjustDown）:
void AdjustDown(int* arr, int parent, int n)
//参数: int* arr: 指向待排序数组的指针
// int parent : 起始父节点在数组中的下标
// int n : 堆中有效数据元素的个数
{
int child = parent * 2 + 1; //左孩子
while (child < n)
{
//小堆: >
//大堆: <
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
//小堆: <
//大堆: >
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}交换函数( Swap ):
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}堆排序函数(HeapSort):
//升序 : 建大堆
//降序 : 建小堆
//堆排序 n*logn
void HeapSort(int* arr, int n)
{
//建堆——向下调整算法建堆 o(n)
for (int i = (n-1-1)/2; i>=0; i--)
{
AdjustDown(arr, i, n);
}
//建堆——向上调整算法建堆 n*logn
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//}
//堆排序 n*logn
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}首先我们先对这个堆排序函数进行讲解:
1. 函数定义:
//堆排序 n*logn
void HeapSort(int* arr, int n) - 功能：对 int 数组 arr 进行堆排序， n 是数组长度
- 复杂度：整体时间复杂度 O(n log n) （建堆 + 排序调整）(后面会有详细讲解)
2. 建堆（向下调整算法， 复杂度 : O(n) ）
//建堆—向下调整算法建堆 o(n)
for (int i = (n-1-1)/2; i>=0; i--)
{
AdjustDown(arr, i, n);
} - 核心逻辑：从最后一个非叶子节点开始，自底向上做向下调整，将原数组转化为堆结构
- 关键细节：
- i = (n-1-1)/2 ：计算最后一个非叶子节点的下标（完全二叉树性质：最后一个节点 n-1 的父节点
是 (n-2) / 2 ）
- AdjustDown(arr, i, n) ：对下标 i 的节点，执行向下调整（大堆/小堆逻辑由 AdjustDown 内部
实现，通常默认大堆用于升序）
时间复杂度:
思路：从最后一个非叶节点（索引 (n/2)- 1）开始，向前逐个对节点执行向下调整，直到根节点。
- 第k层的节点数为 2ᵏ⁻¹（根为第1层），每个节点最多需要向下调整 (堆高度 - k) 次。
- 总操作次数为 ∑(k=1到h-1) 2ᵏ⁻¹ × (h - k)（h为堆高度），通过数学推导可证明该求和结果为
O(n)（具体推导可简化为：每层代价累加后被n线性约束）。所以---- 向下调整法建堆：时间复杂
度为 O(n)
空间复杂度:
没有使用额外数组，仅通过对原数组内部的元素进行交换和调整来构建堆和执行排序，整个过程中
只需要几个临时变量（用于交换元素、记录索引等）。空间复杂度仅由常数级别的临时变量决
定，因此为 O(1)（常数空间）。
3. 注释部分 : 建堆（向上调整算法， 复杂度 : O(n log n) ）
//建堆—向上调整算法建堆n*logn
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//} - 逻辑说明：若取消注释，会用向上调整建堆：
- 从第一个节点开始，逐个插入并向上调整（类似“插入式建堆”）
时间复杂度:
思路：从第2个元素开始（索引1，假设0为起点），逐个将元素插入堆中，每次插入后通过向上调
整维护堆性质。
- 第i个元素（从1到n-1）插入时，最多需要向上调整( log₂i )次（因为其深度为 ( log₂i ) + 1）。
- 总操作次数为 ∑(i=1到n-1) ( log₂i )，该求和结果约为 O(n log n)（与n个元素各自执行O(log n)操
作的总代价相当）, 所以---时间复杂度为 O(n log n)。
空间复杂度:
- 空间复杂度仅由常数级别的临时变量决定，因此为 O(1)（常数空间）。
注意这块是注释部分，为什么呢？因为我们第一步就是要建堆，建堆可以用向下调整法建堆，这个
也可以用向上调整法建堆。但是呢通过二者的时间复杂度和空间复杂度我们可以知道。二者的空间
复杂度相同均为O（1），也说明了在建堆过程中几乎没有消耗额外的空间。但是向下调整算法的
时间复杂度比向上调整算法的时间复杂度更简单，时间复杂度更低，更能显著的提升建堆的效率。
因此实际中堆排序几乎都是采用向下调整法建堆，以此来提高建堆的效率。这也是小编为什么要注
释掉向上调整法建堆的原因。
4. 堆排序（ O(n log n) 复杂度）
//堆排序n*logn
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
} - 核心逻辑：每次把堆顶（当前极值）交换到堆尾，缩小堆范围后重新调整，逐步完成排序
- 逐行拆解：
- int end = n - 1 ：标记当前堆的有效末尾（初始是数组末尾）
- Swap(&arr[0], &arr[end]) ：交换堆顶（下标0）和当前堆尾（下标end） → 把极值“沉淀”到数组
末尾
- AdjustDown(arr, 0, end) ：对剩余区间 [0, end-1] 重新调整堆（修复交换后的堆结构）
- end-- ：缩小堆的有效范围（已排序元素不再参与调整）
时间复杂度:
- 每次循环处理一个元素，共需执行 n-1 次（因为最后一个元素无需处理）。
- 每次向下调整的时间复杂度为 O(log k)（k为当前堆的大小，从n-1逐渐减小到1）。
- 总操作次数为 ∑(k=2到n) O(log k)（k是每次调整时的堆大小），该求和结果为 O(n log n)（因为
log 2 + log 3 + ... + log n ≈ n log n）。所以---- 时间复杂度：O(n log n)
空间复杂度:
- 排序阶段仅使用常数个临时变量（用于交换元素、记录当前堆的边界索引等），所有操作均在原
数组内完成，不依赖额外的存储空间。因此空间复杂度为 O(1)。
3. 复杂度:
原地堆排序的整体时间复杂度为 建堆阶段复杂度 + 排序阶段复杂度：
- 若用向下调整法建堆（O(n)）+ 排序（O(n log n)），整体为 O(n log n)。
- 若用向上调整法建堆（O(n log n)）+ 排序（O(n log n)），整体仍为 O(n log n)（由排序阶段主
导）。
- 空间复杂度始终为 O(1)，体现了原地排序的优势。
但由于向下调整算法建堆的时间复杂度优于向上调整算法建堆的时间复杂度。所以实际排序中都采
用向下调整法建堆。
4. 实例 : 以升序+大堆为例
假设原数组： arr = [3, 1, 4, 1, 5, 9] （ n=6 ）
1. 建堆（向下调整）
- 最后一个非叶子节点下标： i = (6-1-1)/2 = 2 （对应元素 4 ）
- 从 i=2 开始调整，最终构建大堆：
大堆结构（数组表现）：[9, 5, 4, 1, 1, 3]
（堆顶9是最大值，满足父 > 子）
2. 排序循环（交换+调整）
- 第1次循环（ end=5 ）：
- 交换堆顶 9 和堆尾 3 → 数组： [3, 5, 4, 1, 1, 9]
- 调整区间 [0,4] → 重建大堆： [5, 3, 4, 1, 1] → 数组整体： [5, 3, 4, 1, 1, 9]
- end-- → end=4
- 第2次循环（ end=4 ）：
- 交换堆顶 5 和堆尾 1 → 数组： [1, 3, 4, 1, 5, 9]
- 调整区间 [0,3] → 重建大堆： [4, 3, 1, 1] → 数组整体： [4, 3, 1, 1, 5, 9]
- end-- → end=3
- 持续循环：直到 end=0 ，最终数组升序排列： [1, 1, 3, 4, 5, 9]
5. 总结:
在建堆阶段 : 无论用向下调整还是向上调整建堆，只要最终目标是升序排序，都需要建大堆。向上
调整只是建堆的方式不同，不影响堆的类型选择（大堆才能实现升序）。
为什么向上调整建堆也需要大堆？
升序排序的本质是：每次从堆中取出最大值，放到数组末尾，剩余元素再重建堆。这个逻辑和建堆
方式（向下/向上）无关，只和堆的类型（大堆/小堆）有关：
- 大堆的堆顶是最大值，符合“每次取最大值”的需求，最终数组会升序。
- 小堆的堆顶是最小值，若用小堆排序，每次取最小值放末尾，最终数组会降序（若要升序需反向
处理，更复杂）。
若目标是降序排序，无论用向上调整还是向下调整建堆，都需要建小堆。逻辑和升序类似，核心是
匹配“每次取最小值”的需求
排序目标与堆类型的对应关系是固定的，和建堆方式（向上/向下调整）无关：
- 升序 → 大堆（每次取最大值放末尾）
- 降序 → 小堆（每次取最小值放末尾）
| 排序目标 | 建堆类型 |
| 升序 | 建大堆 |
| 降序 | 建小堆 |
无论是向上调整还是向下调整，只要按这个对应关系选择堆类型，就能得到目标排序结果。
在排序阶段 : 排序阶段的核心逻辑是固定的（通过交换堆顶与末尾元素、缩小堆范围并调整堆），
但具体实现会根据建堆类型（大顶堆/小顶堆） 略有差异，因此可以理解为“一种核心方式，两种对
应实现”。
- 若建堆为大顶堆，每次交换后末尾元素是“当前最大值”，最终数组为升序；
- 若建堆为小顶堆，每次交换后末尾元素是“当前最小值”，最终数组为降序。
下面小编在编译器中对版本二堆排序进行一个测试
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUp(int* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//大堆：>
//小堆：<
if (arr[child] > arr[parent])
{
//调整
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//大堆：<
//小堆：>
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
//大堆: >
//小堆：<
if (arr[child] > arr[parent])
{
//调整
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void arrPrint(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//堆排序 n*logn
void HeapSort(int* arr, int n)
{
//建堆——向下调整算法建堆 o(n)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
////建堆——向上调整算法建堆n*logn
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//}
//堆排序n*logn
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
int main()
{
int arr[6] = { 19,15,20,17,13,10 };
printf("排序之前：");
arrPrint(arr, 6);
//堆排序
HeapSort(arr, 6);
printf("排序之后：");
arrPrint(arr, 6);
}仔细观察，小编使用的是向下调整算法建堆，并且建的是大堆，排序时也是大堆。所以最后结果应
该是升序。现在在main函数中有一个待排序的数列arr【6】={19,15,20,17,13,10}，如果是升序，
那么最终结果应该是arr【6】={10,13,15,17,19,20}。下面我们来看编译器所给出的结果。
通过测试的结果我们可以看出和我们预想的结果一样，所以版本二原地堆排序是正确且高效的。
1.3 总结:
如果要用到堆排序来进行排序。推荐第二个版本，也就是原地堆排序，直接进行建堆排序，效率更
高！
以上便是有关堆排序的所有内容。小编在写这篇文章时也是花费了较长的时间，如果大家喜欢的
话，可以给小编一个三连。最后感谢大家的观看！