643 字
3 分钟
堆排序
堆排序(Heap sort)
内容主要来自堆排序算法_阿顾同学的博客-CSDN博客_堆排序，有修改
准备知识
满二叉树
顾名思义，就是全满的都不空的二叉树
完全二叉树
在满二叉树的基础上，从右下角开始缺省（即满二叉树的最下面一层的最右面开始依次缺省，倒数第二层都不行）
大根堆 小根堆
在完全二叉树的基础上，每个结点值都大于其左孩子和右孩子的值，叫大根堆。
每个结点值都小于其左孩子和右孩子的值，叫小根堆。
父结点 左右孩子索引
父结点索引：n / 2 - 1
左孩子索引：2 * i + 1
右孩子索引：2 * i + 2
堆排序原理
- 首先将待排序的数组元素构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
- 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组的个数为n-1
- 将剩余n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
构造大根堆过程
升序排序(大根堆)代码：
#include<stdio.h>#include<iostream>#include<vector>using namespace std;
void Adjust(vector<int> &vec, int start, int end) { int father = start; int child = father * 2 + 1; while (child <= end) {//child<=end的意义是这个孩子节点存在 if (child + 1 <= end && vec[child] < vec[child + 1]) {//右孩子存在，且右孩子大于左孩子 child++; } if (vec[child] > vec[father]) {//最大的子结点大于父亲则交换 swap(vec[child], vec[father]); } //交换后可能破坏了下面的结构，所以继续向下处理 father = child; child = father * 2 + 1; }}
void Heap_sort(vector<int> &vec) { int n = vec.size(); //创建最大堆，从最后一个结点的父结点开始 for (int i = n / 2 - 1; i >= 0; --i) { Adjust(vec, i, n - 1); } //逐个交换，堆顶元素和待排序中的最后一个元素 for (int i = n - 1; i >= 0; --i) { swap(vec[0], vec[i]);//交换堆顶元素和最后一个元素 Adjust(vec, 0, i - 1);//然后把剩下的待排序数组再处理成最大堆结构 }}
int main() { vector<int> vec = { 3, 6, 8, 5, 7 }; int n = vec.size(); Heap_sort(vec); for (int i = 0; i < n; ++i) { cout << vec[i] << " "; } return 0;}