堆排序

堆排序是一种基于堆的排序算法，它的时间复杂度为$O(nlogn)$。

堆排序的基本思想是将待排序的序列构建成一个大根堆或小根堆，然后依次将堆顶元素（最大值或最小值）和堆底元素交换，然后重新调整堆，使得剩余元素继续构成一个大根堆或小根堆，重复进行交换和调整堆的操作，直到整个序列有序。

具体来说，堆排序分为两个主要步骤：

1.建堆：将待排序的序列构建成一个大根堆或小根堆。

2.排序：依次将堆顶元素（最大值或最小值）和堆底元素交换，然后重新调整堆，使得剩余元素继续构成一个大根堆或小根堆，重复进行交换和调整堆的操作，直到整个序列有序。

以下是堆排序的详细过程：

1.建堆：

（1）从最后一个非叶子节点开始，依次向前进行堆化。堆化的过程是将当前节点与其左右子节点进行比较，将最大（或最小）的节点与当前节点交换，然后递归进行堆化。这样可以保证从当前节点到叶子节点的子树都是一个大根堆（或小根堆）。

（2）重复上述过程，直到根节点为止，此时整个序列就已经构建成一个大根堆（或小根堆）。

2.排序：

（1）将堆顶元素与堆底元素交换，将最大（或最小）的元素放到序列的末尾。

（2）重新将堆顶元素进行堆化，使得剩余元素继续构成一个大根堆（或小根堆）。

（3）重复上述过程，直到整个序列有序。

总的来说，堆排序的优点是时间复杂度较低，缺点是实现较为复杂。