heapsort.java

用java写的

package oop;

public class HeapSort implements Sort {
	
	private HeapSort(){}

	public void sort(int[] array) {
		// TODO Auto-generated method stub
		MaxHeap h=new MaxHeap();
        h.init(array);
        for(int i=0;i<array.length;i++)
            h.remove();
        System.arraycopy(h.queue,1,array,0,array.length);

	}
	
	public static Sort getInstance(){//Singleton 最多只产生一个SelectionSort实例
		if (ins==null)
			return new HeapSort();
		else
			return ins;
	}
	
    private static class MaxHeap{
         
        
        void init(int[] data){
            this.queue=new int[data.length+1];
            for(int i=0;i<data.length;i++){
                queue[++size]=data[i];
                fixUp(size);
            }
        }
         
        private int size=0;

        private int[] queue;
                
        public int get() {
            return queue[1];
        }

        public void remove() {
            Swap.swap(queue,1,size--);
            fixDown(1);
        }
        //fixdown
        private void fixDown(int k) {
            int j;
            while ((j = k << 1) <= size) {
                if (j < size && queue[j]<queue[j+1])
                    j++; 
                if (queue[k]>queue[j]) //不用交换
                    break;
                Swap.swap(queue,j,k);
                k = j;
            }
        }
        private void fixUp(int k) {
            while (k > 1) {
                int j = k >> 1;
                if (queue[j]>queue[k])
                    break;
                Swap.swap(queue,j,k);
                k = j;
            }
        }

    }
    
    private static Sort ins=null;

}