数据结构-堆（应用篇）之堆排序法-C和C++的实现

阅读量：5159 次

发布时间：2019-06-13

本文共 1099 字，大约阅读时间需要 3 分钟。

堆排序

关于堆的内容我们已经在上一节中了解了，本节中将给出一个堆的应用-堆排序。

关于堆的概念可以看上一节，入口：

堆排序属于一种选择排序：

步骤如下：

把待排序的数据构建成大顶堆（从大到小排序）。

把堆顶的数据拿出放在数组的第一个元素中。

使用下沉的方法整理堆中的数据。

循环第2,3步，直到堆中所有数据都取出来为止。

这个算法的优缺点如下

优点：时间复杂度低，其中建立堆最多循环了nlong2(n)/2次，时间复杂度为O(nlog2(n))，同样后面重新排序的时间复杂度为O(nlong2(n))，所以整个算法的复杂度为O(nlog2(n))。

缺点：需要建堆，操作繁琐。

综上所述，本排序算法适合排列大量数据时使用。

C语言

取出堆顶元素并把它从堆中删除：

bool MaxHeap_getTopAndMoveIt(MaxHeap *heap,MAXHEAP_ELEM *elem){    *elem = heap->iDatas[0];    MaxHeap_pop(heap,0);    return true;}

MaxHeap_pop()函数为从堆中删除某个数。在上一节中讲过这里不再赘述。

堆排序:

bool HeapSort(MAXHEAP_ELEM buff[],int length){    int i;    MaxHeap heap={
   0};    if(length<=0)        return false;    MaxHeapConstructByBuffer(&heap,buff,10);    for(i=0;i

MaxHeapConstrucByBuffer()函数的作用是把buff[]中的数据建立成堆。在上一节中讲过这里不再赘述。

MaxHeap_getTopAndMoveIt()函数的作用是取出堆顶的元素并放在buff[]的最前边。在堆中，堆顶的的元素为最大值。

测试:

使用堆排序的方法将buffer中的数据从大到小排列：

int main(){    int i;    int buffer[10]={
   0,1,2,3,4,5,6,7,8,9};    HeapSort(buffer,10);    for(i=0;i<10;i++)    {        printf("%d ",buffer[i]);    }    system("pause");    return 0;}