C++堆排序算法

超、凢脫俗 2022-06-15 09:20 169阅读 0赞

堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子结点的值，称为大顶推，或者每个结点的值都小于或等于其左右孩子节点的值，称为小顶堆。

堆排序（Heap  Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，这个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素怒就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行便能得到一个有序序列。

\#include<iostream>  
using namespace std;  
\#define MaxSize 10

typedef struct  
\{  
int length;  
int r\[MaxSize+1\];  
\}SqList;  
  
void HeapAdjust(SqList \*L,int s,int len)  
\{  
int temp;  
temp=L->r\[s\];  
for(int i=2\*s;i<=len;i\*=2)                //沿关键字较大的孩子结点向下筛选  
 \{  
 if(i<len&&L->r\[i\]<L->r\[i+1\])  
    i++;                             //i为关键字中较大的记录的下标  
 if(temp>L->r\[i\])  
break;  
 L->r\[s\]=L->r\[i\];  
 s=i;  
 \}  
L->r\[s\]=temp;  
\}  
  
void swap(SqList \*L,int m,int i)  
\{  
int temp;  
temp=L->r\[m\];  
L->r\[m\]=L->r\[i\];  
L->r\[i\]=temp;  
\}  
  
void HeapSort(SqList \*L)  
\{     
int i,j;  
int len=L->length;  
for(i=len/2;i>0;i--)  
HeapAdjust(L,i,len);         //把L中的r构成一个大顶堆  
for(i=len;i>0;i--)  
 \{   
 swap(L,1,i);              //将堆顶记录和当前未经排序子序列的最后一个记录交换  
 HeapAdjust(L,1,i-1);      //将L->r\[1..i-1\]重新调整为大顶堆  
 \}  
\}

int main()  
\{  
SqList L;  
SqList \*p=&L;  
cin>>L.length;  
for(int i=1;i<=L.length;i++)  
cin>>L.r\[i\];  
HeapSort(p);  
    for(int j=1;j<=L.length;j++)  
cout<<L.r\[j\]<<" ";  
\}

堆排序复杂度分析：

它的运行时间主要消耗在初始构建堆和在重建堆时的反复筛选上。

整体复杂度为O(nlogn)，整个构建堆的时间复杂度为O(n)，重建堆的复杂度为O(nlogn)。

空间复杂度上，它只用一个用来交换的暂存单元，也非常的不错。不过记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序算法。

另外，由于构建堆所需的比较次数比较多，因此，他**并不适合待排序序列个数较少**的情况。