c语言编程笔录

首页 >   > 笔记大全

笔记大全

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

更新时间:2023-08-30

前言

堆排序是一种高效的排序算法,属于选择排序的一种。它利用了二叉堆的特性来进行排序,具有较好的时间复杂度。下面将详细介绍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是数组的长度。堆排序的实现主要依赖于构建堆和下沉操作,通过不断调整堆结构,使得最大(或最小)元素位于堆顶,从而实现排序的目的。