首页 > 代码库 > 堆排序

堆排序

堆排序,要从初始状态调整成大顶堆,然后每次取出顶(此时顶是最大的),用最后一个元素代替顶,再接着排序。

#define LOCAL#include<cstdio>#include<cstdlib>#include<iostream>using namespace std;typedef int ElemType;const int maxSize=10;//从结点low开始把结点low为根的二叉树调成大根堆 void Sift(ElemType R[],int low,int hight){    int i=low,j=2*i;    ElemType temp=R[i];    while(j<=hight)    {        if(j<hight&&R[j]<R[j+1])        {            j=j+1;        }        if(temp<R[j])        {            R[i]=R[j];            i=j;            j=2*i;        }        else        {            break;        }    }    R[i]=temp;}//堆排序函数 void heapSort(ElemType R[],int n){    int i;    ElemType temp;    for(i=n/2;i>=1;--i)    {        Sift(R,i,n);    }    for(i=n;i>=1;--i)    {        temp=R[1];        R[1]=R[i];        R[i]=temp;        Sift(R,1,i-1);    }}void outPut(ElemType R[],int n){    for(int i=1;i<=n;i++)    {        cout<<R[i]<<",";    }    cout<<endl;}int main(){#ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);#endif        ElemType R[maxSize+1];    int i;    for(i=1;i<=maxSize;i++)    {        cin>>R[i];    }    heapSort(R,maxSize);    outPut(R,maxSize);         return 0;}

 

堆排序