C++堆排序算法实例详解

前言

堆排序是一种高效的排序算法，属于选择排序的一种。它利用了二叉堆的特性来进行排序，具有较好的时间复杂度。下面将详细介绍C++中的堆排序算法，并提供一个实例。

代码实现

#include 
using namespace std;

// 下沉函数
void sink(int arr[], int len, int k){
    while(2*k <=len){
        int j=2 * k;
        if(j < len && arr[j] < arr[j+1]){
            j++;
        }
        if(arr[k] >=arr[j]){
            break;
        }
        swap(arr[k], arr[j]);
        k=j;
    }
}

// 堆排序函数
void heapSort(int arr[], int len){
    // 构建堆，从最后一个非叶子节点开始下沉调整
    for(int k=len/2; k >=1; k--){
        sink(arr, len, k);
    }
    // 排序
    while(len > 1){
        swap(arr[1], arr[len]);
        len--;
        sink(arr, len, 1);
    }
}

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

代码解析

上面的代码实现了堆排序算法。

首先，需要实现一个下沉函数sink()用于调整堆。该函数中，参数arr[]表示待操作的数组，len表示数组的长度，k表示当前要进行下沉操作的元素索引。

在heapSort()函数中，我们首先利用sink()函数构建了一个最大堆。然后，我们通过不断将堆顶元素与堆末尾元素交换，并将堆大小缩小1的方式，将最大的元素逐个移动到数组末尾。最终得到的就是升序排列的数组。

总结

通过堆排序算法，我们可以对一个数组进行高效的排序。堆排序的时间复杂度为O(nlogn)，其中n是数组的长度。堆排序的实现主要依赖于构建堆和下沉操作，通过不断调整堆结构，使得最大（或最小）元素位于堆顶，从而实现排序的目的。