注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水禅心

淡若秋菊何妨瘦, 清到梅花不畏寒.

 
 
 

日志

 
 

排序法系列之六---堆排序(C++代码实现)  

2012-12-10 14:20:56|  分类: c++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://blog.csdn.net/liuzhanchen1987/article/details/7367775


[cpp] view plaincopy

    #include<iostream> 
    using namespace std; 
    //return the parent of the ith element 
    int Parent(int i) 
    { 
        return i/2; 
    } 
    //return the left child of the ith element 
    int Left(int i) 
    { 
        return i*2; 
    } 
    //return the right child of the ith element 
    int Right(int i) 
    { 
        return i*2+1; 
    } 
    //build a maxheap from element i to the end  
    void MaxHeap(int *a,int i,int length) 
    { 
        int L,R,temp,larg; 
        L=Left(i); 
        R=Right(i); 
        if(L<=length&&a[L-1]>a[i-1]) 
        { 
            larg=L; 
        } 
        else 
            larg=i; 
        if(R<=length&&a[R-1]>a[larg-1]) 
        { 
            larg=R; 
        } 
        if(larg!=i) 
        { 
            temp=a[larg-1]; 
            a[larg-1]=a[i-1]; 
            a[i-1]=temp; 
            MaxHeap(a,larg,length); 
        } 
    } 
    //build A as the maxheap.the length of A is length 
    void BuildMaxHeap(int *a,int length) 
    { 
        for(int i=length/2;i>0;i--) 
        { 
            MaxHeap(a,i,length); 
        } 
    } 
    //sort A according to the maxheap,Length of A is length 
    void HeapSort(int *a,int length) 
    { 
        int temp; 
        BuildMaxHeap(a,length); 
        for(int i=length;i>0;i--) 
        { 
            temp=a[0]; 
            a[0]=a[i-1]; 
            a[i-1]=temp; 
            length-=1; 
            MaxHeap(a,1,length); 
        } 
    } 
    int main() 
    { 
        int a[10]={1,5,4,8,9,7,6,3,2,10}; 
        HeapSort(a,10); 
        for(int i=0;i<10;i++) 
        { 
            cout<<a[i]<<"  "; 
        } 
        cout<<endl; 
            return 0; 
    } 


以上代码为堆排序的C++实现代码。每一个函数都做了注释。
  评论这张
 
阅读(548)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018