堆排序

package nodelist;

public class HeapSort {
	/**
	 * 堆排序
	 * @param arr
	 */
	public void heapSort(int arr[]){
		int length=arr.length;
		makeMinHeap(arr,length);
		  for(int i=length-1;i>0;i--){
		      swap(arr, 0, i); 
		      adjustHeap(arr,0,i);
		  }  
	}
	public static void main(String[] args) {
		HeapSort hs = new HeapSort();
		int[] arr = new int[] { 5, 6, 2, 3, 4, 7, 8, 9 };
		hs.heapSort(arr);
		for (int el : arr) {
			System.out.println(el);
		}
	}
	//构建最小堆
	private void makeMinHeap(int[] arr, int length) {
		for(int i=(length-1)/2;i>=0;i--){
			adjustHeap(arr,i,length);
		}
	}
	
	//数组从0开始  所以左子节点为parent*2+1
	private void adjustHeap(int[] arr,int parent,int n){
		int child=parent*2+1;
		while(child<n){
			if((child+1<n)&&(arr[child+1]<arr[child]))
				child++;
			if(arr[child]>=arr[parent])
				break;
			swap(arr,parent,child);
			parent=child;
			child=parent*2+1;
		}
	}
	/**
	 * 交换数据
	 */
	public void swap(int array[], int leftpoint, int rightpoint) {
		int temp = array[leftpoint];
		array[leftpoint] = array[rightpoint];
		array[rightpoint] = temp;
	}

}