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

韬光养晦

路漫漫其修远兮,吾将上下而求索

 
 
 

日志

 
 

堆排序Java实现  

2008-08-15 12:01:10|  分类: JAVA |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       首先将这n个元素按关键码建成堆,将堆顶元素输出,得到n个元素中关键码最小(或最大)的元素。然后,再对剩下的n-1个元素建成堆,输出堆顶元素,得到n个元素中关键码次小(或次大)的元素。如此反复,便得到一个按关键码有序的序列。称这个过程为堆排序。

       因此,实现堆排序需解决两个问题:
       1. 如何将n个元素的序列按关键码建成堆;
       2. 输出堆顶元素后,怎样调整剩余n-1个元素,使其按关键码成为一个新堆。

       首先,讨论输出堆顶元素后,对剩余元素重新建成堆的调整过程。
       调整方法:设有m个元素的堆,输出堆顶元素后,剩下m-1个元素。将堆底元素送入堆顶,堆被破坏,其原因仅是根结点不满足堆的性质。将根结点与左、右子女中较小(或小大)的进行交换。若与左子女交换,则左子树堆被破坏,且仅左子树的根结点不满足堆的性质;若与右子女交换,则右子树堆被破坏,且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。称这个自根结点到叶子结点的调整过程为筛选。

      再讨论对n个元素初始建堆的过程。
     建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。n个结点的完全子树成为堆,之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。




public class HeapSort {
    //该函数对从i/2为根节节点的子树到整个树进行筛选,从而达到建立一个堆的目的。
    public static void setHeap(int[] a){
        for(int i=a.length;i>=0;i--){
            filter(a,i,a.length-1);
        }
    }

    //对以数组a的第i个节点为根节点的子树为根节点的树进行筛选,筛选截止到e点包括e点。
    //若此处不用e则每次筛选会树中末尾的废弃节点一并进行筛选,会出现错误。
    public static void filter(int[] a,int i,int e){
        if(i>=a.length-1 || i>e)
            return ;
        int temp;
        //树除了根 其余部分都是堆 这里将树的大根 同 较小的树交换。递归
        if(2*i+1<=e && 2*i+2<=e){
            if(a[i]<a[2*i+1] && a[i]<a[2*i+2])
                return;
            if(a[2*i+1]<a[2*i+2]){
                temp=a[i];
                a[i]=a[2*i+1];
                a[2*i+1]=temp;
                if(2*i+1<=e)
                    filter(a,2*i+1,e);
            }else{
                temp=a[i];
                a[i]=a[2*i+2];
                a[2*i+2]=temp;
                if(2*i+2<=e)
                    filter(a,2*i+2,e);
            }
        }else if(2*i+1 == e){
            if(a[i]<a[2*i+1])
                return;
            temp=a[i];
            a[i]=a[2*i+1];
            a[2*i+1]=temp;
            if(2*i+1<=e)
                filter(a,2*i+1,e);
        }
    }
    //以下进行对排序,取出堆顶,然后把最后一个元素放到堆顶,再进行筛选,即完成排序。
    private static int[] sort(int[] a) {
        //先输出a
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]);
            System.out.print(" ");
        }
        System.out.println();
        //建立堆
        setHeap(a);
        //建立堆之后输出a
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]);
            System.out.print(" ");
        }
        System.out.println();
        //
       
        int[] b=new int[a.length];
        for(int i=0;i<b.length;i++){
            b[i]=a[0];
            a[0]=a[a.length-i-1];
            filter(a,0,a.length-i-2);
        }
        return b;
    }
   
    public static void main(String[] args){
        int[] a=new int[args.length];
        for(int i=0;i<args.length;i++){
            a[i]=Integer.parseInt(args[i]);
        }
       
        int[] b=sort(a);
       
        for (int i=0;i<b.length;i++){
            System.out.print(b[i]);
            System.out.print(" ");
        }
        System.out.println();
    }   
}


  评论这张
 
阅读(918)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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