【数据结构】堆排序

一、堆排序

1、堆排序介绍

堆排序（Heapsort）可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

在学习数据结构堆时，知道可以通过“建堆操作”和“元素出堆操作”实现堆排序。

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。

2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。在实际中，我们通常使用一种更加优雅的实现方式，避免额外空间消耗。

想要了解数据结构堆的相关知识可以查看链接【数据结构】堆-CSDN博客

2、算法流程

设数组的长度为 n ，堆排序的流程如下。

1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶。

2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1 ，已排序元素数量加 1 。

3. 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。

4. 循环执行第 2. 步和第 3. 步。循环 n−1 轮后，即可完成数组排序。

3、代码实现

#include <iostream>#include <vector>using namespace std;​void siftDown(vector<int> &maxHeap,int len,int i){while (true){// 判断节点 i, l, r 中值最大的节点，记为 maint l = 2 * i + 1, r = 2 * i + 2, ma = i;if (l < len && maxHeap[l] > maxHeap[ma]){ma = l;}if (r< len && maxHeap[r] > maxHeap[ma]){ma = r;}// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出if (i == ma){break;}swap(maxHeap[i], maxHeap[ma]);// 循环向下堆化i = ma;}}​void heapSort(vector<int> &nums){int len = nums.size();//建堆操作：堆化除叶节点以外的其他所有节点for (int i = len / 2 - 1; i >= 0; --i) {siftDown(nums, len, i);}// 从堆中提取最大元素，循环 n-1 轮for (int i = len - 1; i > 0; --i){// 交换根节点与最右叶节点（交换首元素与尾元素）swap(nums[0], nums[i]);// 以根节点为起点，从顶至底进行堆化siftDown(nums, i, 0);}}​int main(){int arr[] = { 1,20,6,34,100,33,35,20 };int len = sizeof(arr) / sizeof(arr[0]);​vector<int> nums(arr, arr + len);heapSort(nums);for (auto num : nums){std::cout << num << " ";}std::cout << std::endl;}

4、算法特性

• 时间复杂度为 O(nlog⁡n)、非自适应排序：建堆操作使用 O(n) 时间。从堆中提取最大元素的时间复杂度为 O(log⁡n) ，共循环 n−1 轮。

• 空间复杂度为 O(1)、原地排序：几个指针变量使用 O(1) 空间。元素交换和堆化操作都是在原数组上进行的。

• 非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化。