实现堆排序

堆排序是一种基于完全二叉树的排序算法，它的时间复杂度为 O(nlogn)。下面给出一份 C++ 的实现代码：

#include <iostream>
#include <vector>
using namespace std;

// 调整堆
void adjustHeap(vector<int>& nums, int parent, int len) {
    int temp = nums[parent];
    int child = 2 * parent + 1;
    while (child < len) {
        if (child + 1 < len && nums[child] < nums[child + 1]) {
            child++;
        }
        if (temp >= nums[child]) {
            break;
        }
        nums[parent] = nums[child];
        parent = child;
        child = 2 * parent + 1;
    }
    nums[parent] = temp;
}

// 堆排序
void heapSort(vector<int>& nums) {
    int len = nums.size();
    // 构建大顶堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(nums, i, len);
    }
    // 依次将最大值放到数组末尾
    for (int i = len - 1; i >= 1; i--) {
        swap(nums[0], nums[i]);
        adjustHeap(nums, 0, i);
    }
}

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    heapSort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

首先，我们需要定义一个调整堆的函数 `adjustHeap`，它接收一个数组 `nums`，一个父节点 `parent` 和数组长度 `len`。在调整堆的过程中，我们将父节点与其左右子节点进行比较，将最大值放到父节点的位置，并继续向下比较，直到找到合适的位置。

接着，我们需要定义堆排序的函数 `heapSort`，它接收一个数组 `nums`。在堆排序中，我们首先需要构建一个大顶堆，即将数组转换为一棵完全二叉树，使得每个父节点的值都大于其左右子节点的值。然后，我们每次将最大值放到数组的末尾，并重新调整堆，直到所有的元素都被排序。

最后，我们在主函数中定义一个数组 `nums`，并调用 `heapSort` 函数对其进行排序。输出结果为：1 1 2 3 3 4 5 5 5 6 9。