C++排序代码：堆排序

/*
chatGPT写的，十分清爽！
堆排序：数组排序前建立最大堆，排序时不断把堆顶最大值放到最后，并维护待排数组为最大堆，完成排序。
稳定性：不稳定排序
时间复杂度：O(n log n)
空间复杂度：O(1)
推荐B站up主“请叫我AXin”的讲解视频《排序算法：堆排序【图解+代码】》
*/

#include <iostream>
#include <vector>

// 下沉操作，将元素移动到正确的位置
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);
    }
}

int main() {
    std::vector<int> arr = { 12, 11, 13, 5, 6, 7 };
    int n = arr.size();

    std::cout << "原始数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    heapSort(arr);

    std::cout << "排序后数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}