C++ 实现排序算法：堆排序详解及代码示例

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

堆排序的基本思想是：先将待排序的序列构建成一个大根堆（或小根堆），然后不断取出堆顶元素，将其放到已排序的序列中，并调整剩余元素构成的堆，重复这个过程直到所有元素都被取出。

下面是堆排序的具体实现：

1. 构建大根堆

从最后一个非叶子节点开始，对每个节点进行下沉操作，使其满足大根堆的性质。

void adjustHeap(vector<int>& nums, int i, int len) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < len && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < len && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        adjustHeap(nums, largest, len);
    }
}

void buildHeap(vector<int>& nums) {
    int len = nums.size();
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(nums, i, len);
    }
}

2. 堆排序

每次将堆顶元素取出，放到已排序的序列中，然后调整剩余元素构成的堆。

void heapSort(vector<int>& nums) {
    int len = nums.size();
    buildHeap(nums);
    for (int i = len - 1; i >= 0; i--) {
        swap(nums[0], nums[i]);
        adjustHeap(nums, 0, i);
    }
}

完整代码如下：

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

void adjustHeap(vector<int>& nums, int i, int len) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < len && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < len && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        adjustHeap(nums, largest, len);
    }
}

void buildHeap(vector<int>& nums) {
    int len = nums.size();
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(nums, i, len);
    }
}

void heapSort(vector<int>& nums) {
    int len = nums.size();
    buildHeap(nums);
    for (int i = len - 1; i >= 0; i--) {
        swap(nums[0], nums[i]);
        adjustHeap(nums, 0, i);
    }
}

int main() {
    vector<int> nums = { 6, 5, 3, 1, 8, 7, 2, 4 };
    heapSort(nums);
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << ' ';
    }
    return 0;
}