堆排序（C++实现）

参考：

1. 面试官：请写一个堆排序_哔哩哔哩_bilibili
2. C++实现排序算法_c++从小到大排序-CSDN博客

堆的基本概念

1. 堆排实际上是利用堆的性质来进行排序。堆可以看做一颗完全二叉树。

2. 堆分为两类：

   1. 最大堆（大顶堆）：除根节点外，堆的每个父节点都大于其孩子节点。
   2. 最小堆（小顶堆）：除根节点外，堆的每个父节点都小于其孩子节点。
   3. 最大堆和最小堆示意图：

3. 数据结构包含逻辑结构和存储结构，对于堆来说：

   1. 堆的逻辑结构是完全二叉树
   2. 堆的存储结构可以是链式存储，也可以是顺序存储。在堆排序中我们基于的存储结构是顺序存储。
   3. 顺序存储示意图：（以最大堆为例）

堆排序

1. 堆排序主要分为三个步骤：
   1. 建堆
   2. 交换数据
   3. 重复步骤1,2
2. 建堆。首先说说建堆，因为我们要对数组进行排序，这个数组里元素原本的排列是无规则的，为了能通过堆对数组进行排序，我们需要进行“建堆”操作，从而使得数组的排序符合堆的要求。根据上文可知，堆可以分为两种，一种是最大堆，另一种是最小堆。既然有两种堆，我们应该基于哪种类别来建堆呢？这就要取决于我们的排序形式了，如果是升序（从小到大），则需要建最大堆；如果是降序（从大到小），则需要建最小堆。以下都以升序（建最大堆为例）。
3. 交换数据。交换什么数据呢？这里直接给出结论，是交换堆（数组）索引为0的元素和末尾元素（堆的最后一个元素）。因为我们已经建好堆了，且我们堆的存储结构是顺序结构，即根节点（只最大的节点）存储在数组的第一位（索引为0），这是我们将这个数与数组最后一个数交换位置，就完成了数组中最大元素的排序（因为最大的元素肯定在数组最后一个位置）。
4. 交换完数据后，对于新的堆（新的二叉树）来说，是不满足最大堆的条件的（因为发生了位置交换），这时就需要重新建堆，重新建堆有别于初次建堆，因为我们已经固定了最大元素的位置，所以之后建堆不应该让这个最大的元素参与进来。
5. 参考代码如下：
   最大堆建堆：

/*** 堆化* 大根堆（大顶堆/最大堆），小的数往下沉*/
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;
}