C++ 堆排序算法实现及减治法应用详解

堆排序是一种基于堆数据结构的排序算法，其时间复杂度为 O(nlogn)，其中 n 为待排序序列的长度。堆排序的具体实现过程如下：

构建初始堆：将待排序序列构建成一个大根堆或小根堆，以大根堆为例，从最后一个非叶子节点开始，依次将其与左右子节点进行比较，将最大值交换到父节点位置，直到整个序列构成一个大根堆。
排序：将堆顶元素与序列最后一个元素交换位置，然后将堆的大小减一，再对剩余元素重新构建大根堆，直到整个序列有序。

减治法在堆排序中的应用主要是在构建初始堆的过程中。在每次将最大值交换到父节点位置后，我们可以只对被交换的子节点进行下沉操作，而不必对整个子树进行重新构建。这样可以减少不必要的操作，提高算法效率。

例如，对于一个长度为 n 的序列，其最后一个非叶子节点的下标为 n/2-1，我们可以从该节点开始，依次向前遍历每个非叶子节点，对每个节点进行下沉操作，这样就可以构建出一个大根堆。这样做的时间复杂度为 O(n)，比从头开始构建堆的时间复杂度 O(nlogn) 要低。