经典排序算法：堆排序 (Heap Sort)

什么是堆排序？

堆排序是一种基于二叉堆数据结构的排序算法。它利用堆的性质（最大堆或最小堆）来选择元素。

算法步骤

1. 建堆 (Build Heap): 将无序的输入数组构建成一个最大堆。最大堆的性质是父节点的值总是大于或等于其子节点。
2. 排序 (Sort): a. 将堆顶元素（最大值）与堆的最后一个元素交换。 b. 将堆的大小减一。 c. 对新的堆顶元素进行“堆化”(heapify)操作，以维持最大堆的性质。 d. 重复步骤 a-c，直到堆的大小为 1。

代码实现 (C++)

#include <vector>
#include <algorithm> // For std::swap

// 维护最大堆性质
void heapify(std::vector<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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

复杂度分析

• 时间复杂度: O(n log n)。建堆是 O(n)，每次调整是 O(log n)。
• 空间复杂度: O(1)，是原地排序算法。
• 稳定性: 堆排序是不稳定的排序算法。