堆排序

package sort;

import java.util.ArrayList;
import java.util.List;

public class HeapSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[] = {16,4,10,14,7,9,3,2,8,1,0,23,15,13};
//        array= arrayAdapter(array);
//        maxHeapify2(array,0);
//        buildMaxHeap(array);
        heapSort2(array);
        print(array);
       
    }

    private static void print(List<Integer> list) {
        for(int i=0;i<list.size();i++){
            System.out.println((list.get(i)));
        }
    }

    public static List<Integer> heapSort(int[] a){
        buildMaxHeap(a);
        List<Integer> list = new ArrayList<Integer>();
        for(int i=a.length-1;i>0;i--){
            int larger = a[0];
            list.add(larger);
            a[0] = a[i];
//            a[i] = larger;
           System.arraycopy(a, 0, a, 0, i);
           maxHeapify2(a, 0);
        }
        return list;
    }
    public static void  heapSort2(int[] a){
        buildMaxHeap(a);
        for(int i=a.length-1;i>0;i--){
            int larger = a[0];
            a[0] = a[i];
            a[i] = larger;
           maxHeapify3(a,i, 0);
        }
    }
    private static void maxHeapify3(int[] array, int length, int i) {
        int j = length;
        int l = 2*i+1;
        int r = 2*i +2;
        int largest = 0;
        if(l<j && array[l]>array[i])
            largest = l;
        else
            largest = i;
        if(r<j && array[r]>array[largest])
            largest = r;
        if(i != largest){//需要重新堆化
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            maxHeapify3(array,length,largest);
        }
        System.out.println("largest:  "+largest +" int i = "+i);
    }

    public static void maxHeapify(int[] array,int i){
            int j = array.length;
            int l = 2*i;
            int r = 2*i +1;
            int largest = 0;
            if(l<=j && array[l]>array[i])
                largest = l;
            else
                largest = i;
            if(r<=j && array[r]>array[largest])
                largest = r;
            if(i != largest){//需要重新堆化
                int temp = array[i];
                array[i] = array[largest];
                array[largest] = temp;
                maxHeapify(array,largest);
            }
    }
    public static void buildMaxHeap(int[] a){
        int j = a.length;
        double d = Math.floor(j/2.0);
        int i = (int)d;
        for(;i >=0;i--){
            maxHeapify2(a, i);
        }
    }
    public static void maxHeapify2(int[] array,int i){
        int j = array.length;
        int l = 2*i+1;
        int r = 2*i +2;
        int largest = 0;
        if(l<j && array[l]>array[i])
            largest = l;
        else
            largest = i;
        if(r<j && array[r]>array[largest])
            largest = r;
        if(i != largest){//需要重新堆化
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            maxHeapify2(array,largest);
        }
}
    public static int[] arrayAdapter(int[] array){
        int a[] = new int[array.length+1];
        a[0] = Integer.MAX_VALUE;
        for(int j=0;j<array.length;j++){
            a[j+1] = array[j];
        }
        return a;
    }
    public static void print(int[] array){
        for(int i=0,j=array.length;i<j;i++){
            System.out.println(array[i]);
        }
    }
}