堆排序

import org.junit.Test;

/** 
 * @author [e-mail] 
 * @creation date 2010-9-9 上午11:55:33 
 * 
 * 堆排序
 * 
 * 
 * 步骤
 * 1：建堆
 * while(数组长度大于1){
 * 2：堆的”根元素“ 交换 到 数组尾部
 * 3：剩余部分向下堆重排
 * }
 */

public class HeapSort {
	
	public void sort(int[] array,int size){
		int temp; 
		int unsorted;
		//建堆
		createHeap(array,size);
		unsorted = size;
		
		while(unsorted > 1){
			unsorted--;

			temp = array[0];
			array[0] = array[unsorted];
			array[unsorted] = temp;
			downHeapSort(array,unsorted);
		}
		
	}

	/*
	 * 建堆（大顶堆）
	 * 
	 * while(data[k]还不是根元素，data[k]比他的双亲大){
	 * 		将data[k]和 其双亲节点交换，将K重新设置为它的双亲下标。
	 * }
	 */
	private void createHeap(int[] array, int size) {
		//建堆(向上建堆)
		for(int i = 1; i < size; i++){
			int k = i;//待添加元素下标
			//若k未到堆顶，且下标k对应的元素值大于其父节点的元素值
			while( k!=0 && array[k] > array[parent(k)]){
				int temp = array[parent(k)];
				array[parent(k)] = array[k];
				array[k] = temp;
				
				k = parent(k);
			}
		}
	}

	private int parent(int k) {
		return (k-1)/2;
	}

	/**
	 * 向下堆重排：
	 * 前提：除堆顶外，剩余部分是一个堆
	 *  
	 * @param array
	 * @param size
	 */
	public void downHeapSort(int[] a, int size) {
		//向下堆重排
		int current;//当前元素下标
		int bigChildIndex;//最大子元素下标
		boolean heapOkay;//是否已经建好堆
		
		int count = 0;
		
		current = 0;
		heapOkay = false;//初始状体:未排完
		
		//堆未建好，当前下标对应的元素不是叶子节点
		while((!heapOkay) && (! isLeaf(current, size))){
			
			bigChildIndex = getBigChild(a,current,size);//获得当前元素的最大孩子节点下标
			
			if(a[current]<a[bigChildIndex]){//如果当前元素小于最大孩子节点则交换之
				int temp = a[current];
				a[current] = a[bigChildIndex];
				a[bigChildIndex] = temp;
				
				current = bigChildIndex;
				
			}else{
				heapOkay = true;//已经排完
			}
		}
			
		}

	private int getBigChild(int[] array, int current,int size) {
		//获取堆中current中比较大的孩子下标
		if(((current*2+2)>size-1)){//单节点，直接返回该节点
			return current*2+1;
		}else{
			return ( array[current*2+1] >= array[current*2+2] ) ? (current*2+1):(current*2+2);
		}
	}

	private boolean isLeaf(int current,int size) {
		// 判断当前位置是否叶子节点（注意：此处判断条件是小于不能等于）
		return ((current*2 + 1)< size)? false : true;
	}
		
		
	@Test
	public void test(){
		HeapSort heap = new HeapSort();
		int[] array = new int[10];
		
		for(int i = 0; i <array.length ;  i++){
			array[i] = (int)(Math.random()*100);
		}
		System.out.print("初始值\n");
		DisplayUnit.showArray(array);

		heap.sort(array, array.length);

		System.out.print("\n 排完序：");
		DisplayUnit.showArray(array);
		}
	
	}