首页 > 其他 > 详细

堆排序

时间:2014-05-21 22:02:02      阅读:419      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
package com.bupt.acm;

import java.util.Scanner;

public class HeapSort {

    private int getLeft(int i){
    
        return 2*(i+1)-1;
    }
    private int getRight(int i){
        return 2*(i+1);
    }
    public void heapSort(int[] numb){
        int length=numb.length;
        int size=length;
        //根据数组建堆
        for(int i=length/2;i>=0;i--){
            buildMinHeap(numb,i,size);
        }
        //将最小值移到最后元素并调整
        int tmp=0;
        for(int i=size-1;i>=0;i--){
            tmp=numb[0];
            numb[0]=numb[i];
            numb[i]=tmp;
            buildMinHeap(numb, 0,i);
        }
    }
    private void buildMinHeap(int[] numb,int i,int length){
        int largest=i;
        int left=getLeft(i);
        int right=getRight(i);
        
        if(left<length&&numb[largest]<numb[left]){
            largest=left;
        }
        if(right<length&&numb[largest]<numb[right]){
            largest=right;
        }
        if(largest==i){
            return;
        }else{
            int tmp=numb[i];
            numb[i]=numb[largest];
            numb[largest]=tmp;
            buildMinHeap(numb, largest,length);
        }
    }
    private void buildMaxHeap(int[] numb, int i,int length) {
        // TODO Auto-generated method stub
        int largest=i;
        int left=getLeft(i);
        int right=getRight(i);
        
        if(left<length&&numb[largest]>numb[left]){
            largest=left;
        }
        if(right<length&&numb[largest]>numb[right]){
            largest=right;
        }
        if(largest==i){
            return;
        }else{
            int tmp=numb[i];
            numb[i]=numb[largest];
            numb[largest]=tmp;
            buildMaxHeap(numb, largest,length);
        }
    }
    public static void main(String[] args){
        int[] result=null;
        int n=0;
        Scanner scanner=new  Scanner(System.in);
        HeapSort heapSort=new HeapSort();
        while(scanner.hasNext()){
            n=scanner.nextInt();
            result=new int[n];
            for(int i=0;i<n;i++){
                result[i]=scanner.nextInt();
            }
            heapSort.heapSort(result);
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
    }
}
bubuko.com,布布扣

bubuko.com,布布扣

堆排序,布布扣,bubuko.com

堆排序

原文:http://www.cnblogs.com/csxf/p/3739224.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!