堆排序（C++实现）
参考：
- 面试官：请写一个堆排序_哔哩哔哩_bilibili
- C++实现排序算法_c++从小到大排序-CSDN博客
堆的基本概念
-
堆排实际上是利用堆的性质来进行排序。堆可以看做一颗完全二叉树。
-
堆分为两类：
- 最大堆（大顶堆）：除根节点外，堆的每个父节点都大于其孩子节点。
- 最小堆（小顶堆）：除根节点外，堆的每个父节点都小于其孩子节点。
- 最大堆和最小堆示意图：
-
数据结构包含逻辑结构和存储结构，对于堆来说：
- 堆的逻辑结构是完全二叉树
- 堆的存储结构可以是链式存储，也可以是顺序存储。在堆排序中我们基于的存储结构是顺序存储。
- 顺序存储示意图：（以最大堆为例）
堆排序
- 堆排序主要分为三个步骤：
- 建堆
- 交换数据
- 重复步骤1,2
- 建堆。首先说说建堆，因为我们要对数组进行排序，这个数组里元素原本的排列是无规则的，为了能通过堆对数组进行排序，我们需要进行“建堆”操作，从而使得数组的排序符合堆的要求。根据上文可知，堆可以分为两种，一种是最大堆，另一种是最小堆。既然有两种堆，我们应该基于哪种类别来建堆呢？这就要取决于我们的排序形式了，如果是升序（从小到大），则需要建最大堆；如果是降序（从大到小），则需要建最小堆。以下都以升序（建最大堆为例）。
- 交换数据。交换什么数据呢？这里直接给出结论，是交换堆（数组）索引为0的元素和末尾元素（堆的最后一个元素）。因为我们已经建好堆了，且我们堆的存储结构是顺序结构，即根节点（只最大的节点）存储在数组的第一位（索引为0），这是我们将这个数与数组最后一个数交换位置，就完成了数组中最大元素的排序（因为最大的元素肯定在数组最后一个位置）。
- 交换完数据后，对于新的堆（新的二叉树）来说，是不满足最大堆的条件的（因为发生了位置交换），这时就需要重新建堆，重新建堆有别于初次建堆，因为我们已经固定了最大元素的位置，所以之后建堆不应该让这个最大的元素参与进来。
- 参考代码如下：
最大堆建堆：
/**
* 堆化
* 大根堆（大顶堆/最大堆），小的数往下沉
*/
void maxHeapify(vector<int> &nums, int pos, int len)
{
// (pos << 1) + 1就是2*pos+1，对应该节点的左子节点
// (pos << 1) + 2就是2*pos+2，对应该节点的右子节点
int child = (pos << 1) + 1;
while (child < len)
{
if (child + 1 < len && nums[child + 1] > nums[child])
{
child = child + 1;
}
if (nums[pos] > nums[child])
{
return;
}
else
{
swap(nums[pos], nums[child]);
pos = child;
child = (pos << 1) + 1;
}
}
}
最小堆建堆：
/**
* 堆化
* 小根堆（小顶堆/最小堆），大的数往下沉
*/
void minHeapify(vector<int> &nums, int pos, int len)
{
// (pos << 1) + 1就是2*pos+1，对应该节点的左子节点
// (pos << 1) + 2就是2*pos+2，对应该节点的右子节点
int child = (pos << 1) + 1;
while (child < len)
{
if (child + 1 < len && nums[child + 1] < nums[child])
{
child = child + 1;
}
if (nums[pos] < nums[child])
{
return;
}
else
{
swap(nums[pos], nums[child]);
pos = child;
child = (pos << 1) + 1;
}
}
}
堆排序：
/**
* 堆排序
*/
void heapSort(vector<int> &nums)
{
// 每次交换完数据后要len--，让排序好的元素不参与建堆
for (int len = nums.size(); len > 0; len--)
{
// (len - 2) >> 1就是（len-2)/2，这样能找到最后一个非叶子结点
for (int i = (len - 2) >> 1; i >= 0; i--)
{
minHeapify(nums, i, len);// 最小堆建堆，对应降序
// maxHeapify(nums, i, len);// 最大堆建堆，对应升序
}
// 每进行一次交换就要重新堆化，且重新堆化时堆的大小要对应减1（因为堆末尾的元素已经排好序了）
swap(nums[0], nums[len - 1]);
}
}
堆排序测试用例
#include <iostream>
#include <vector>
using namespace std;
/**
* 堆化
* 大根堆（大顶堆/最大堆），小的数往下沉
*/
void maxHeapify(vector<int> &nums, int pos, int len)
{
int child = (pos << 1) + 1;
while (child < len)
{
if (child + 1 < len && nums[child + 1] > nums[child])
{
child = child + 1;
}
if (nums[pos] > nums[child])
{
return;
}
else
{
swap(nums[pos], nums[child]);
pos = child;
child = (pos << 1) + 1;
}
}
}
/**
* 堆化
* 小根堆（小顶堆/最小堆），大的数往下沉
*/
void minHeapify(vector<int> &nums, int pos, int len)
{
int child = (pos << 1) + 1;
while (child < len)
{
if (child + 1 < len && nums[child + 1] < nums[child])
{
child = child + 1;
}
if (nums[pos] < nums[child])
{
return;
}
else
{
swap(nums[pos], nums[child]);
pos = child;
child = (pos << 1) + 1;
}
}
}
/**
* 堆排序
*/
void heapSort(vector<int> &nums)
{
for (int len = nums.size(); len > 0; len--)
{
for (int i = (len - 2) >> 1; i >= 0; i--)
{
minHeapify(nums, i, len);// 最小堆建堆，对应降序
// maxHeapify(nums, i, len);// 最大堆建堆，对应升序
}
// 每进行一次交换就要重新堆化，且重新堆化时堆的大小要对应减1（因为堆末尾的元素已经排好序了）
swap(nums[0], nums[len - 1]);
}
}
int main(int argc, char const *argv[])
{
vector<int> nums = {5, 3, 2, 63, 56, 8, -1, 3, 0, -222};
heapSort(nums);
for (auto num : nums)
{
cout << num << " ";
}
cout << endl;
return 0;
}