如何使用C++实现堆排序算法

一、什么是堆排序算法

堆排序算法是一种基于完全二叉树的排序算法，它指定了一个最大/最小堆的概念，通过不断将根节点移动到数组的末尾，并对余下的元素重建堆，最后达到排序的目的。堆排序算法的时间复杂度为O(nlogn)。

二、堆排序算法的实现步骤

1. 构建初始堆：将n个元素构建成初始堆，从最后一个非叶子结点开始，自下而上执行堆调整（maxHeap）。

2. 将堆顶元素放到末尾：交换堆顶元素和序列末尾元素，堆大小减1。

3. 重建堆：对新的堆顶元素进行heapify操作（maxHeap），将其放到正确的位置。

4. 重复上述步骤，直到堆大小为1。

三、C++实现堆排序算法

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

// 构建初始堆
void maxHeapify(vector<int>& nums, int heapSize, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;
    if (left < heapSize && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < heapSize && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != index) {
        swap(nums[index], nums[largest]);
        maxHeapify(nums, heapSize, largest);
    }
}

// 堆排序
void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 构建初始堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        maxHeapify(nums, n, i);
    }
    // 将堆顶元素放到末尾，重建堆
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        maxHeapify(nums, i, 0);
    }
}

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

四、堆排序算法的优化

堆排序算法可以有许多优化，比如使用最小堆代替最大堆，使用堆内存储的元素下标代替额外空间存储堆元素，使用堆化的方式构建初始堆等等。

其中，使用堆化的方式构建初始堆可以减少时间复杂度，堆化方式有自上而下的堆化和自下而上的堆化。自上而下的堆化相比自下而上的堆化来说，需要更多的swap操作，但在堆偏小的情况下会比较适用。

// 自上而下的堆化
void maxHeapify(vector<int>& nums, int heapSize, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;
    while (left < heapSize) {
        if (nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(nums[index], nums[largest]);
            index = largest;
            left = 2 * index + 1;
            right = 2 * index + 2;
            largest = index;
        } else {
            break;
        }
    }
}

五、总结

堆排序算法是一种快速稳定的排序算法，通过构建最大/最小堆的方式对无序序列进行排序。C++实现堆排序只需要实现maxHeapify和heapSort两个函数，便可以对序列进行排序。在实际应用中，还可以通过堆化方式构建初始堆，进一步提高堆排序的效率。