堆排序

概述

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

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

动画展示

思路解析

1. 初始序列：91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22
2. 根据完全二叉树用数组存储，那么在数组中的下标是有规律的，左孩子是父节点下标的两倍加一，右孩子是父节点下标的两倍加二。而且最后一个父节点是数组总长度 / 2 - 1.
3. 所以可以调整成堆，这里以大顶堆来说，每次将第一个元素和最后一个元素交换，这样就可以将最大的元素放在最后，待排序规模减一
4. 递归实现

算法性能

时间复杂度

堆排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。这是因为构建初始堆的时间复杂度为O(n)，而每次移除堆顶元素并重新构建堆的时间复杂度为O(logn)。由于这个过程需要重复n次，所以总的时间复杂度为O(nlogn)。堆排序的时间复杂度在最坏情况下也为O(nlogn)，这意味着无论输入数据的初始状态如何，堆排序都能保持相对稳定的性能。

空间复杂度

堆排序的空间复杂度为O(1)。这是因为堆排序是一种原地排序算法，它只涉及到元素之间的交换和移动，不需要额外的存储空间来存放数据。这使得堆排序在处理大型数据集时非常高效，因为它避免了存储器占用的问题。

稳定性

根据堆排序的基本原理和常见实现，它通常被认为是不稳定的排序算法。

代码实现

//堆化(参数：数组，数组长度，从某个节点开始)
void heapify(vector<int>& v, int n, int i) {
	//初始化最大值为i以及左右孩子
	int largest = i, left = i * 2 + 1, right = i * 2 + 2;
	//如果左孩子没有越界并且大于父节点，将largest指向左孩子
	if (left<n && v[left]>v[largest])largest = left;
	//同理
	if (right<n && v[right]>v[largest])largest = right;
	if (largest != i) {
		swap(v[largest], v[i]);
		//继续下沉
		heapify(v, n, largest);
	}
}
void heap_sort(vector<int>& v) {
	int n = v.size();
	//i指向最后一个父节点
	for (int i = n / 2 - 1; i >= 0; i--) {
		heapify(v, n, i);
	}
	//将最后一个和第一个交换，每次交换待排序规模减一
	for (int i = n - 1; i >= 0; i--) {
		swap(v[0], v[i]);
		//重新堆化
		heapify(v, i, 0);
	}
}