如何使用C++中的堆排序算法- 技术经验 -卓越飞翔博客

如何使用C++中的堆排序算法

堆排序是一种常用的排序算法，它利用堆的性质进行排序。堆排序分为两个步骤：建堆和排序。在本文中，我们将学习如何使用C++语言实现堆排序算法，并给出具体的代码示例。

堆的定义和性质
堆是一个完全二叉树，可以分为最大堆和最小堆两种。最大堆的任意节点的值都大于或等于其子节点的值，最小堆的任意节点的值都小于或等于其子节点的值。在堆排序算法中，我们通常使用最大堆。

堆的实现可以使用数组来表示，数组的下标可以表示堆中的节点编号。对于任意节点i，它的父节点为(i-1)/2，左子节点为2i+1，右子节点为2i+2。

建堆算法
建堆算法是堆排序的第一步，它的目的是将一个无序的数组构建成一个堆。建堆的思路是从数组的最后一个非叶子节点开始，对每个节点进行下沉操作，使得它满足堆的性质。

下面是建堆算法的C++代码示例：

// 下沉操作，将指定节点下沉到合适的位置
void downAdjust(int arr[], int parent, int length) {
    int child = 2 * parent + 1; // 左子节点的下标
    int temp = arr[parent]; // 保存要下沉的节点的值
    
    while (child < length) {
        // 如果有右子节点，且右子节点的值大于左子节点的值，则选择右子节点
        if (child+1 < length && arr[child] < arr[child+1]) {
            child++;
        }
        
        // 如果父节点的值大于等于子节点的值，则下沉结束
        if (temp >= arr[child]) {
            break;
        }
        
        // 将子节点的值上移，代替父节点
        arr[parent] = arr[child];
        parent = child;
        child = 2 * parent + 1;
    }
    
    // 将要下沉的节点插入合适的位置
    arr[parent] = temp;
}

// 建堆算法，将无序数组构建成最大堆
void buildHeap(int arr[], int length) {
    // 从最后一个非叶子节点开始，依次进行下沉操作
    for (int i = (length-2) / 2; i >= 0; i--) {
        downAdjust(arr, i, length);
    }
}

排序算法
建堆完成后，我们可以进行排序操作，排序的思路是每次取出堆顶元素，将其与堆尾元素交换，然后对剩下的部分重新进行下沉操作。

下面是堆排序算法的C++代码示例：

// 堆排序算法
void heapSort(int arr[], int length) {
    // 1. 构建最大堆
    buildHeap(arr, length);
    
    // 2. 排序
    for (int i = length - 1; i > 0; i--) {
        // 将堆顶元素与堆尾元素交换
        swap(arr[i], arr[0]);
        
        // 对剩下的部分重新进行下沉操作
        downAdjust(arr, 0, i);
    }
}

示例和测试
下面是一个使用堆排序算法的示例和测试：

#include <iostream>

// 输出数组元素
void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 主函数
int main() {
    int arr[] = {4, 1, 3, 9, 7};
    int length = sizeof(arr) / sizeof(int);
    
    std::cout << "排序前的数组：" << std::endl;
    printArray(arr, length);
    
    // 使用堆排序算法进行排序
    heapSort(arr, length);
    
    std::cout << "排序后的数组：" << std::endl;
    printArray(arr, length);
    
    return 0;
}

输出结果为：

排序前的数组：
4 1 3 9 7 
排序后的数组：
1 3 4 7 9

通过以上示例和测试，我们可以看到使用C++语言实现的堆排序算法可以正确地对数组进行排序。

总结：
本文介绍了如何使用C++语言实现堆排序算法，并给出了具体的代码示例。堆排序算法的核心在于建堆和排序两个步骤，其中建堆的思路是从最后一个非叶子节点开始进行下沉操作，排序的思路是每次取出堆顶元素，将其与堆尾元素交换，并对剩下的部分重新进行下沉操作。通过实际测试，我们可以验证堆排序算法的正确性和稳定性。

相关推荐