堆排序练习：POJ 2388

关于堆排序请参看：http://128kj.iteye.com/blog/1679094
POJ2388题意：
  【输入】第一行为n，接下来n行分别为一个数；
  【输出】这n个数排序后的中位数
样例：
Sample Input

5
2
4
1
3
5
Sample Output

3

分析：好象用多种排序法都可以AC，这里先用堆排序，主要是复习一下堆排序代码。

排一次序后输出中位数，但效率太低了。这里先不管了。

import java.util.Scanner;
public class Main {   
  
    public static void main(String[] args) {  
     Scanner in=new Scanner(System.in);
     int n=in.nextInt();
     int[] array =new int[n+1];   
    // array[0]=100;   不参与,下标从1开始
     for(int i=1;i<=n;i++)
        array[i]=in.nextInt();
     heapSort(array);//堆排序
     System.out.println(array[n / 2+1 ]); 
     //堆排序的结果
    // for(int i=1;i<=n;i++)
    //    System.out.print(array[i]+"  ");
     }   
 
    //把a,b位置的值互换    
    public static void swap(int[] array, int a, int b) {    
        //临时存储child位置的值    
       int temp = array[a];    
       array[a]=array[b];    
       array[b]=temp;    
    }    

     /*将数组调整成堆
      *根据树的性质建堆，树节点前一半一定是分支节点，即有孩子的，所以我们从这里开始调整出初始堆
      */     
     public static void adjust(int[] array){   
        for (int i = array.length / 2; i > 0; i--)     
            adjust(array,i, array.length-1);     
  
       
      }   

    /**   
     * 调整堆，使其满足堆得定义   
     * @param i   
     * @param n   
     */     
    public static void adjust(int[] array,int i, int n) {     
          
        int child;     
        for (; i <= n / 2; ) {     
            child = i * 2;     
            if(child+1<=n&&array[child]<array[child+1])     
                child+=1;/*使child指向值较大的孩子*/     
            if(array[i]< array[child]){     
                swap(array,i, child);     
                /*交换后，以child为根的子树不一定满足堆定义，所以从child处开始调整*/     
                i = child;     
                  
            }  else break;   
        }     
    }     
     
   //对一个最大堆heap排序   
    public static void heapSort(int[] array) {     
          adjust(array);//建堆
        for (int i = array.length-1; i > 0; i--) {     
      /*把根节点跟最后一个元素交换位置，调整剩下的n-1个节点，即可排好序*/     
            swap(array,1, i);     
            adjust(array,1, i - 1);     
        }     
    }     
  

}