堆排序（HeapSort）是一种基于比较的排序算法，它利用了完全二叉树（通常存储在数组中）的性质来构建一个大顶堆或小顶堆，并通过调整堆结构实现排序。下面是堆排序的基本步骤：

1. 构建堆：

• 首先将待排序的序列构造成一个最大堆（大顶堆），或者最小堆（小顶堆）。对于升序排列，我们通常构建大顶堆，即父节点的值大于或等于其子节点的值。

• 从最后一个非叶子节点开始（即最后一个元素的父亲节点），逐个调整该节点及其子节点构成的子树，使其满足堆的性质。

2. 交换堆顶元素与末尾元素：

• 将堆顶元素（即当前未排序序列的最大元素或最小元素）与其最后一个元素进行交换，这样保证了已排序区间的最后一个元素是当前最大的（或最小的）。

• 然后将堆的大小减一，表示新的待排序区间范围缩小。

3. 重新调整堆：

• 对剩余的元素组成的堆进行调整，使之再次成为一个大顶堆（或小顶堆）。

• 重复步骤2的过程，直到整个序列有序。

C++代码示例：

#include <iostream>using namespace std;void heapify(int arr[], int n, int i) {	int largest = i; // 初始化为根节点索引	int left = 2 * i + 1;	int right = 2 * i + 2;	// 检查左孩子是否大于根节点	if (left < n && arr[left] > arr[largest])		largest = left;	// 检查右孩子是否大于当前最大的节点	if (right < n && arr[right] > arr[largest])		largest = right;	// 如果最大的不是根节点，则交换它们	if (largest != i) {		swap(arr[i], arr[largest]);		// 递归地对新的根节点调用heapify		heapify(arr, n, largest);	}}void heapSort(int arr[], int n) {	// 构建大顶堆	for (int i = n / 2 - 1; i >= 0; i--)		heapify(arr, n, i);	// 一次又一次删除堆顶元素并重新调整堆	for (int i = n - 1; i >= 0; i--) {		// 将堆顶元素和最后一个元素交换		swap(arr[0], arr[i]);		// 调整剩下的n-i-1个元素以重新形成堆		heapify(arr, i, 0);	}}

堆排序的时间复杂度在最好、最坏和平均情况下均为O(n log n)，其中n是数组的长度。由于堆排序不需要额外的空间，因此它的空间复杂度为O(1)。同时，堆排序是不稳定的排序算法，即相等的元素可能会改变原有的相对顺序。