C++堆排序详解

一、堆排序简介

堆排序是一种基于比较的排序算法，其时间复杂度为O(n log n)。它的基本思想是将待排序的序列构造成一个堆，然后依次取出堆顶元素（最大或最小值），并将剩余待排序元素重新调整为堆。

堆是一种特殊的树形数据结构，它通常用数组来实现。堆满足以下两个条件：

• 任意节点的值都不大于（或不小于）其左右儿子节点的值，称为大根堆（或小根堆）
• 堆总是一棵完全二叉树

二、堆排序过程

堆排序的过程可以分为两个阶段：

1、构建堆

首先将待排序的序列构建成一个大根堆（也可以是小根堆），具体过程如下：

• 从最后一个非叶子节点（即len/2-1）开始，依次将每个节点和其子节点进行比较，如果节点值小于其子节点值，则将其与最大值节点进行交换
• 交换后，被交换的节点位置变为其子节点位置，重复上述过程，直到所有节点都被交换到最后一层为止
• 构建好的堆就是一个符合大根堆或小根堆条件的序列

2、排序

接下来，我们需要将堆顶元素（最大或最小值）取出，然后将剩余待排序元素重新构建堆，依次进行如下操作：

• 将堆顶元素与最后一个元素交换，最后一个元素为已排序的数据，堆大小减一
• 将剩余待排序元素重新构建堆

重复以上操作，直到堆中只剩下一个元素，排序完成。

三、C++堆排序代码

#include <iostream>
using namespace std;

// 建立大根堆
void adjustHeap(int arr[], int len, int i) {
    int j = i;
    // 左子节点
    int left = 2 * i + 1;
    // 右子节点
    int right = 2 * i + 2;
    // 找到最大值
    if (left < len && arr[left] > arr[j]) {
        j = left;
    }
    if (right < len && arr[right] > arr[j]) {
        j = right;
    }
    // 如果当前节点已经是最大值，退出递归
    if (j != i) {
        swap(arr[i], arr[j]);
        adjustHeap(arr, len, j);
    }
}

// 堆排序
void heapSort(int arr[], int len) {
    // 构建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    // 排序
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        adjustHeap(arr, i, 0);
    }
}

int main() {
    int arr[] = {9, 2, 4, 1, 3, 7, 8, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, len);
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

四、堆排序优化

以上代码是最基本的堆排序算法，但是我们可以通过一些优化，进一步提升堆排序的效率。

1、堆化优化

在建堆过程中，我们可以将数组从后往前遍历，对于每个节点，只需将其与其子节点进行比较，而不必和所有子孙节点都进行比较。这样可以减少比较次数，提升效率。

// 建立大根堆
void adjustHeap(int arr[], int len, int i) {
    int j = i;
    // 左子节点
    int left = 2 * i + 1;
    // 右子节点
    int right = 2 * i + 2;
    // 找到最大值
    if (left < len && arr[left] > arr[j]) {
        j = left;
    }
    if (right < len && arr[right] > arr[j]) {
        j = right;
    }
    // 如果当前节点已经是最大值或者当前节点没有子节点，退出递归
    if (j != i) {
        swap(arr[i], arr[j]);
        adjustHeap(arr, len, j);
    }
}

2、堆排序优化

在排序过程中，我们可以将堆大小作为参数传入，不必每次都重新计算。同时，在将堆顶元素与最后一个元素交换位置后，仅需对根节点进行堆化，可以减少一半的比较次数。

// 堆排序
void heapSort(int arr[], int len) {
    // 构建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    // 排序
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        adjustHeap(arr, i, 0);
    }
}

五、总结

堆排序是一种高效的排序算法，通过构建堆结构，可以使排序过程的时间复杂度达到O(n log n)。C++提供了丰富的数据结构和算法库，可以更方便地实现堆排序，同时优化堆化和排序过程，可以进一步提高算法的效率。