目录
方法
- 第一步：
我们将待排序数组形象成一个堆结构，并将其调整为最大堆
（堆结构：左孩子的下标是2i+1， 右孩子下标 2i+2)
（最大堆的特点：在这个堆结构里，任何一个父节点的值都大于其子节点的值）
- 第二步：
将堆顶元素与待排序数组（假设待排序的数据数量为nums)最后一个元素进行交换，swap(&vec[0], &vec[nums-1]);
- 第三步：
待排序的数据量减少一个, 即nums--; 将待排序数组重新调整成最大堆结构，重复第二步，循环n-1次，将所有数据排序完成。
初始化堆（将数组调整成最大堆）从最后一个父节点开始调整（即 i = n/2-1）
示例代码
#include<iostream>
#include<vector>
using namespace std;
// 将以 father 为根的子树调整为最大堆
void adjust(vector<int>& vec, int father, int end) {
int child = father * 2 + 1; // 左孩子节点
while (child <= end) {
if (child + 1 <= end && vec[child] < vec[child + 1]) { // 如果右孩子存在且比左孩子大，则选择右孩子作为交换对象
child = child + 1;
}
if (vec[father] < vec[child]) { // 如果父节点小于孩子节点，则交换父节点和孩子节点的值
swap(vec[father], vec[child]);
}
else {
break; // 如果父节点已经大于等于孩子节点，则说明已经满足最大堆性质，退出循环
}
father = child; // 更新父节点和孩子节点的位置
child = father * 2 + 1;
}
}
// 堆排序函数
void Headsort(vector<int>& vec) {
// 建立最大堆
for (int i = vec.size() / 2 - 1; i >= 0; i--) {
adjust(vec, i, vec.size() - 1);
}
// 排序阶段
for (int i = vec.size() - 1; i >= 1; i--) {
swap(vec[0], vec[i]); // 将当前堆顶元素放到数组末尾
adjust(vec, 0, i - 1); // 重新调整堆，只需要考虑前 i - 1 个元素
}
}
int main() {
// 测试数据
vector<int>vec{ 5,7,3,9,4,8,2,9,1 };
int n = vec.size();
// 调用堆排序函数
Headsort(vec);
// 输出排序后的结果
for (auto x : vec) {
cout << x << " ";
}
return 0;
}
复杂度分析
平均时间复杂度:O(nlogn)
n个节点的完全二又树有 log 2(n+1)层创建最大堆过程中，两两元素相互比较共比较 n-1次，在交换过程中可能破坏某个最大堆结构，我们可以假设共调整k次可以恢复最大堆结构，故建堆过程时间复杂度为 O(n+k)=O(n)。 每个根节点最大下降(l0g2(n+1))-1层，每下降一层需比较两次，假设每个根节点都下降到最底层，则下降一个根节点的时间复杂度为 O(2((l0g2(n+1)) n-1))，共有 n-1 个根节点需要下降，则下降过程的时间复杂度为
O((n-1)2(log2(n+1)-1))=0(n*logn)。
综上所述，堆排序时间复杂度为
O(n)+O(nlogn)=0(nlogn)。
空间复杂度:0(1) 在原数组上操作，即使用了常数级空间O(1)