九大排序算法之堆排序
排序算法：堆排序（HeapSort）
关键定义：二叉堆，不稳定的选择排序算法
定义：堆排序 标准定义
堆排序（Heap Sort）是基于二叉堆数据结构实现的一种原地、不稳定的选择排序算法，其核心是利用堆 “父节点与子节点间的大小约束特性”，通过构建初始堆和反复提取堆顶极值 + 重新堆化的操作，将无序序列逐步转换为有序序列。
一 ，前置知识点：
1 二叉堆
堆是一个完全二叉树，主要存在两种类型：
大顶堆：每个父节点的值 ≥ 其左右子节点的值，堆顶（根节点）是整个堆的最大值。
小顶堆：每个父节点的值 ≤ 其左右子节点的值，堆顶是整个堆的最小值。
注：采用大顶堆则堆排序为升序，采用小顶堆位降序
2 链表和数组这两种线性存储结构
堆排序中对于元素的储存大多采用数组结构，原因如下：
| 特性 | 数组 | 链表（单链表） |
|---|---|---|
| 存储结构 | 连续内存空间 | 非连续节点 + 指针串联 |
| 访问方式 | 随机访问（O (1)） | 顺序访问（O (n)） |
| 插入 / 删除（中间） | O (n)（需移动元素） | O (1)（仅改指针，找前驱 O (n)） |
| 长度特性 | 静态固定（动态数组需扩容） | 动态可变 |
| 内存开销 | 仅存数据，开销小 | 数据 + 指针，额外开销大 |
| 缓存友好性 | 优（连续预加载） | 差（分散无预加载） |
| 内存分配要求 | 需连续大空间，要求高 | 小块分散空间，要求低 |
| 代码实现复杂度 | 简单 | 较高（需处理指针） |
结构先天适配：堆是完全二叉树，节点排列有规律，能和数组的连续索引一一对应，通过简单公式即可定位父 / 子节点，这是数组成为堆最优存储结构的根本原因；
效率完美匹配：数组的 O (1) 节点定位、缓存友好、原地存储特性，让堆排序的核心操作（堆化、构建堆、堆顶交换）保持高效，确保堆排序 O (n log n) 的时间复杂度和 O (1) 的空间复杂度；
短板完全规避，优势充分发挥：数组的通用缺点（连续内存、静态长度）在堆排序的固定数据量、无动态增删场景下可忽略，而链表的核心优点（动态增删、内存灵活）在堆排序中无意义，核心短板（定位慢、开销大、缓存差）却会直接让堆排序的效率大幅下降，甚至丧失算法优势。
二，堆排序实现过程（数组实现）
假设有如下二叉树
步骤 1：确定堆化的起始节点（最后一个非叶子节点）
构建初始大顶堆时，无需对叶子节点执行堆化（叶子节点无左右子节点，本身已满足堆性质），只需从最后一个非叶子节点开始，从后向前依次对每个节点执行「向下堆化」操作。
最后一个非叶子节点索引计算：
数组最后一个元素的索引为n-1，其父节点即为最后一个非叶子节点，索引公式为 (n-1 - 1) // 2 = (n-2) // 2。
示例计算：n=11，最后一个非叶子节点索引 = (11-2)//2 = 4，即数组中索引 0~4 为非叶子节点，5~10 为叶子节点，堆化仅需处理索引 {0,1,2,3,4}，且从最大索引 4 开始向前执行。
步骤 2：构建初始大顶堆（核心：向下堆化）
向下堆化定义：对指定节点，从该节点向叶子节点遍历，将其与「左右子节点中的最大值」比较，若当前节点小于最大值则交换，交换后继续对新位置的节点执行堆化，直到当前节点≥所有子节点（满足大顶堆性质）或到达叶子节点。
构建逻辑：从最后一个非叶子节点（示例索引 4）开始，向前遍历至根节点（索引 0），对每个节点依次执行向下堆化，最终让整个数组满足大顶堆性质。
部分示例构建过程（数组 {20,30,90,40,70,110,60,10,100,50,80}）：
堆化索引 3（值 40）：左右子节点为索引 7（10）、8（100），最大值为 100（索引 8），40<100，交换后索引 3 值为 100、索引 8 值为 40，该节点堆化完成；
堆化索引 4（值 70）：左右子节点为索引 9（50）、10（80），最大值为 80（索引 10），70<80，交换后索引 4 值为 80、索引 10 值为 70，该节点堆化完成；
构建结果：原数组转换为大顶堆{110,100,90,40,80,20,60,10,30,50,70}，堆顶（索引 0）为整个数组的最大值 110，满足「所有父节点≥子节点」的大顶堆性质。
补充：：必须满足大顶堆性质，完成交换后会破坏之前排序顺序，需要重新检测排序，如下图的a[3]
步骤 3：提取堆顶极值并重新堆化（核心排序过程）
初始大顶堆构建完成后，堆顶为当前无序序列的最大值，通过「堆顶与无序序列最后一个元素交换」，将最大值放到最终有序位置，随后缩小无序序列范围，对新堆顶执行向下堆化，恢复大顶堆性质。重复此操作，直到无序序列长度为 1，整个数组即完成升序排序。
核心规则：
- 设当前无序序列的长度为
len（初始 len=n），堆顶为索引 0，无序序列最后一个元素为索引len-1； - 交换后，索引
len-1为有序元素，无序序列长度更新为len-1，仅对新堆顶（索引 0）执行向下堆化即可恢复堆性质（其余节点仍满足堆约束）。
示例排序过程（初始大顶堆 {110,100,90,40,80,20,60,10,30,50,70}，n=11）：
- 第二次操作（len=10）：交换堆顶 100（索引 0）与无序序列最后一个元素 50（索引 9），数组变为
{50,80,90,40,70,20,60,10,30,100,110}，有序元素为 100、110（索引 9-10）；无序序列长度更新为 9，堆化后恢复大顶堆为{90,80,60,40,70,20,50,10,30,100,110}； - 重复上述操作：每次交换堆顶与当前无序序列最后一个元素，缩小无序序列范围并重新堆化，直到无序序列长度 len=1；
- 最终结果：所有元素完成有序排列，数组变为
{10,20,30,40,50,60,70,80,90,100,110}，升序排序完成。
第一次操作（len=11）：交换堆顶 110（索引 0）与无序序列最后一个元素 70（索引 10），数组变为{70,100,90,40,80,20,60,10,30,50,110}，有序元素为 110（索引 10）；无序序列长度更新为 10，对索引 0 执行向下堆化，恢复大顶堆为{100,80,90,40,70,20,60,10,30,50,110}；
三、堆排序的核心特性
1 时间复杂度
- 构建初始堆：时间复杂度为O(n)（非 O (nlogn)，因叶子节点无需堆化，上层节点堆化次数少，整体累计为线性时间）；
- 提取堆顶并堆化：共执行 n-1 次，每次堆化的时间复杂度为 O (logn)（堆的高度为 log₂n+1），总时间复杂度为 O (nlogn)；
- 整体时间复杂度：O(n) + O(nlogn) = O(nlogn)，且最好、最坏、平均情况均为 O (nlogn)，是少数时间复杂度稳定的高效排序算法。
2 空间复杂度
堆排序的所有操作均在原数组上完成，仅使用常数个临时变量（如索引、交换临时值），无额外的动态内存分配，空间复杂度为 O (1)，属于原地排序算法。
3 稳定性
堆排序是不稳定排序算法，原因是堆化过程中的「跨位置交换」会破坏相同值元素的相对顺序。
示例：数组{5,3,5,1}构建大顶堆后为{5,3,5,1}，第一次交换堆顶 5（索引 0）与最后一个元素 1（索引 3），数组变为{1,3,5,5}，原数组中第一个 5（索引 0）与第二个 5（索引 2）的相对顺序被改变。
4 适用场景
- 适合大规模数据排序：10 万、100 万级别的数据排序效率远高于冒泡、选择、插入等简单排序，与快速排序、归并排序处于同一高效梯队；
- 适合内存有限的场景：原地排序 O (1) 的空间复杂度，无需额外的内存存储临时数据，适配嵌入式、内存受限的设备；
- 无需稳定排序的场景：因堆排序不稳定，若要求相同值元素的相对顺序不变，需选择归并排序、冒泡排序等稳定算法。
定义代码示例
// 堆排序：调整堆结构（最大堆） bool XSort::Heapify(int* pArray, int nLength,int nIndex) { if (!pArray || nLength <= 0 || nIndex < 0 || nIndex >= nLength) { return false; } int nEndIndex = nLength - 1; // 需要判断存在 int nLeftIndex = 2 * nIndex + 1; // 左孩子索引 for (; nLeftIndex <= nEndIndex; nIndex = nLeftIndex, nLeftIndex = 2 * nIndex + 1) // 循环构成大根堆 { if (nLeftIndex < nEndIndex && pArray[nLeftIndex] < pArray[nLeftIndex + 1]) nLeftIndex += 1; if (pArray[nIndex] < pArray[nLeftIndex]) swap(pArray[nIndex], pArray[nLeftIndex]); else break; } return true; }
// 堆排序实现 bool XSort::HeapSort(int* pArray, int nLength) { if (!pArray|| nLength <= 1) { return false; } int nEndIndex = nLength - 1; for (int i = (nEndIndex - 1) / 2; i >= 0; --i) { Heapify(pArray, nLength, i); } while (nEndIndex > 0) { swap(pArray[0], pArray[nEndIndex]); nEndIndex--; Heapify(pArray, nEndIndex + 1, 0); // 重新堆化根节点，堆的长度为nEndIndex+1 } return true; }测试代码
//九大排序 #include "XSort.h" #include <iostream> // -------------------------- 测试核心函数 -------------------------- int main() { // 1. 定义超大数组参数（可调整大小，建议根据电脑性能修改，10万/50万/100万） const int BIG_ARRAY_SIZE = 100000; // 超大数组长度（10万个元素，可按需增大） // 2. 动态分配原始超大数组（避免栈溢出，静态数组无法存储超大数据） int* pOriginalArray = new int[BIG_ARRAY_SIZE]; if (pOriginalArray == nullptr) { std::cout << "原始数组内存分配失败！" << std::endl; return -1; } // 3. 初始化随机数种子（确保每次运行随机数不同） srand((unsigned int)time(nullptr)); // 4. 填充超大数组为随机整数（值域：0~9999，保证计数排序高效运行） std::cout << "正在初始化 " << BIG_ARRAY_SIZE << " 个随机元素的超大数组..." << std::endl; for (int i = 0; i < BIG_ARRAY_SIZE; ++i) { pOriginalArray[i] = rand() % 10000; // 随机数范围：0~9999 } std::cout << "数组初始化完成！" << std::endl << std::endl; // 5. 创建XSort对象 XSort sortTool; // 6. 定义临时数组（用于存储原始数组副本，避免排序后破坏原始数据） int* pTempArray = new int[BIG_ARRAY_SIZE]; if (pTempArray == nullptr) { std::cout << "临时数组内存分配失败！" << std::endl; delete[] pOriginalArray; pOriginalArray = nullptr; return -1; } // 7. 测试前5种排序算法并统计时间 clock_t start, end; double elapsedTime; // 耗时（单位：秒） // -------------------------- 测试7：堆排序 -------------------------- std::memcpy(pTempArray, pOriginalArray, BIG_ARRAY_SIZE * sizeof(int)); std::cout << "\n开始测试【堆排序】..." << std::endl; start = clock(); bool heapResult = sortTool.HeapSort(pTempArray, BIG_ARRAY_SIZE); end = clock(); elapsedTime = (double)(end - start) / CLOCKS_PER_SEC; if (heapResult) std::cout << "堆排序成功！耗时：" << elapsedTime << " 秒" << std::endl; else std::cout << "堆排序失败！" << std::endl; // 8. 释放动态内存，避免内存泄漏 delete[] pOriginalArray; pOriginalArray = nullptr; delete[] pTempArray; pTempArray = nullptr; std::cout << "\n所有排序测试完成！" << std::endl; return 0; }测试结果
