技术交流QQ群:1027579432，欢迎你的加入！
一.概述
- 堆排序是简单选择排序的改进算法，简单选择排序在待排序的个数据中选择一个最小的元素需要进行n-1次的比较，但是并没有将每一次循环的结果保存下来，在下一次循环中，有很多比较已经在上一次的循环中做过了，但由于上一次循环时没有保存这些比较结果，所以下一次循环时又要重复这些比较操作，因此数据的比较次数较多。堆排序可以做到每次在选择最小记录的同时，根据比较结果对其他元素做出相应的调整。
二.大顶堆与小顶堆介绍
大顶堆.jpg
小顶堆.jpg
- 从上面的两幅图可以看出，它们都是完全二叉树。下面给出堆的定义：
- 大顶堆：每个结点的值都大于或等于其左右孩子结点的值，根结点的值一定是所有结点中最大的
- 小顶堆：每个结点的值都小于或等于其左右孩子结点的值，根结点的值一定是所有结点中最小的
- 按照层序遍历，给结点从1开始编号，则结点之间满足下面的关系,其中1<=i<=[n/2]:
大顶堆中结点之间的关系.jpg
- 按照层序遍历，将上图中的大顶堆存入数组中，小顶堆类似，如下图所示:
大顶堆按层序遍历存入数组中.jpg
三.原理
- 首先，将待排序的n个元素构造成一个大顶堆(小顶堆也可以，下面以大顶堆为例)。此时，这个序列的最大值就是大顶堆的根结点；然后，将大顶堆的根结点与堆数组中的最后一个元素进行交换，交换后，大顶堆的根结点存放的就是堆数组中的最后一个元素，大顶堆的根结点中存储的原始的最大值被移走啦；接着，将剩下的n-1个元素重新调整后，构造成一个新的大顶堆，重复上面的步骤，被移动的元素就构成了一个有序的数据。下面解决两个问题:(1)怎么将一个无序的数据构造成一个大顶堆?;(2)怎么将剩余的元素重新调整，构成一个新的大顶堆?
四.堆排序过程
构建大顶堆.jpg
重新调整.jpg
5.堆排序的完整代码
#include <iostream>
using namespace std;
#define N 9
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct{
int r[MAXSIZE+1];
int len;
}Sqlist;
void show(Sqlist L){
for(int i = 1; i <= L.len; i++)
cout << L.r[i] << " ";
cout << endl;
}
void Swap(Sqlist *L, int i, int j){
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
// 堆排序需要考虑的两个问题：
/*
1.如何将一个无序的序列构造成一个大/小顶堆
2.在输出堆顶元素后，怎么调整剩余的元素，使剩余的元素成为一个新的大/小顶堆
*/
// 堆调整函数
// 已知L->r[s..m]中的记录的关键字除L->r[s]之外均满足堆的定义，需要调整的关键字是L->r[s],使L->r[s...m]成为一个大顶堆
void HeapAdjust(Sqlist *L, int s, int m){
int temp, j;
temp = L->r[s]; // L->r[s]是不满足大顶堆条件的结点，需要进行调整
for(j = 2*s; j <= m; j*=2){ // 循环遍历当前结点s的左右孩子j，因为是完全二叉树，所以左孩子的序号是2*s，右孩子的序号是2*s+1
if(j < m && L->r[j] < L->r[j+1]) // L->r[j]是左孩子,L->r[j+1]是右孩子,j<m说明当前的孩子结点不是完全二叉树的最后一个结点
++j; // L->r[j] < L->r[j+1]说明左孩子小于右孩子,说明最大值在右孩子结点上
if(temp >= L->r[j]) // 当前的结点s就是最大值，不需要调整，直接跳出循环
break;
L->r[s] = L->r[j]; // 将当前结点s与左右孩子结点j进行交换，调整成大顶堆
s = j;
}
L->r[s] = temp;
}
// 下面的程序是以大顶堆为例！！！
// 堆排序函数
void HeapSort(Sqlist *L){
int i;
// 构建一个大顶堆,时间复杂度是O(n)
for(i = L->len / 2; i >0; i--) // 将L中的r[i]构造成一个大顶堆，i从L->len / 2开始是因为它们都是有左右孩子的结点
HeapAdjust(L, i, L->len);
// 重建一个大顶堆，时间复杂度是O(nlogn)
for(i = L->len; i > 1; i--){ // 逐步将每个最大值的根结点与完全二叉树中的末尾元素进行交换，并且再调整使其成为一个新的大顶堆
Swap(L, 1, i); // 将大顶堆根结点与完全二叉树中最后一个元素交换，移除旧的大顶堆的根结点，现在剩余结点总数是i-1
HeapAdjust(L, 1, i-1); // 将L->r[1...i-1]重新调整为大顶堆，需要调整的元素索引是大顶堆的根结点1和剩余结点总数i-1
}
}
int main(){
Sqlist L;
int d[N] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
for(int i = 0; i < N; i++)
L.r[i+1] = d[i];
L.len = N;
cout << "堆排序前: ";
show(L);
cout << "堆排序后: ";
HeapSort(&L);
show(L);
return 0;
} - STL实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 堆排序：（最大堆，有序区）。从堆顶把堆顶元素弹出来放在有序区，再恢复堆。
// 打印元素
void PrintV(vector<int>& v){
for(auto &e: v){
cout << e << ' ';
}
cout << endl;
}
// 堆排序核心代码
void HeapSortCore(vector<int>& v, int start, int end){
// 建立父节点和子节点指针
int parent = start;
int son = parent * 2 + 1;
while(son <= end){ // 子节点在范围内才做比较
if(son + 1 <= end && v[son] < v[son+1]){ // 先比较两个子节点大小，选择最大的
son++;
}
if(v[parent] > v[son]){ // 如果父节点大于子节点，代表堆调整完毕，跳出循环
return;
}
else{ // 否则，交换父子节点的内容，再继续子节点和孙节点比较
swap(v[parent], v[son]);
parent = son;
son = parent * 2 + 1;
}
}
}
// 堆排序----外部调用接口
void HeapSort(vector<int>& v){
// 初始化，i从最后一个父节点从下向上开始调整
int n = v.size();
for(int i = n/2 - 1; i>=0; --i){
HeapSortCore(v, i, n-1);
}
// 先将第一个元素和已经排好序的元素前一位做交换，再重新调整堆
for(int i=n-1; i > 0; --i){
swap(v[0], v[i]);
HeapSortCore(v, 0, i-1);
}
}
int main(){
vector<int> v{7, 30, 16, 4, 1, 2, 9};
cout << "堆排序前: ";
PrintV(v);
HeapSort(v);
cout << "堆排序后: ";
PrintV(v);
return 0;
} 六、堆排序时间复杂度总结：
- 平均时间复杂度：O(nlogn)
- 最好情况：O(nlogn)
- 最坏情况：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
京公网安备 11010502036488号