堆排序（C++实现）

参考：

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

堆的基本概念

堆排实际上是利用堆的性质来进行排序。堆可以看做一颗完全二叉树。
堆分为两类：
1. 最大堆（大顶堆）：除根节点外，堆的每个父节点都大于其孩子节点。
2. 最小堆（小顶堆）：除根节点外，堆的每个父节点都小于其孩子节点。
3. 最大堆和最小堆示意图：
数据结构包含逻辑结构和存储结构，对于堆来说：
1. 堆的逻辑结构是完全二叉树
2. 堆的存储结构可以是链式存储，也可以是顺序存储。在堆排序中我们基于的存储结构是顺序存储。
3. 顺序存储示意图：（以最大堆为例）

堆排序

堆排序主要分为三个步骤：
1. 建堆
2. 交换数据
3. 重复步骤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;
}