堆排序

堆排序
     原理 ：对的父节点总是大于或者小于子节点，所以根节点一定是最大值或者最小值，
利用这个性质，首先构建初始堆，然后将堆的顶点与末尾的值交换， 然后再次调整堆（排除末尾的值），反复此过程

public static void main(String[] args) {
		int[] a = {5,3,6,2,1,9,4,8,7};
		heap(a);
	}
	
	
	public static void heap(int[] array){
		buildMaxHeap(array);
		for(int i = array.length - 1 ; i > 0; i--){
			
			System.out.println("调整交换中 :" + i + Arrays.toString(array));
			
			int temp = array[0];
			array[0] = array[i];
			array[i] = temp;

			System.out.println("调整前 :" + i + Arrays.toString(array));
			adjust(array, i , 0);
			System.out.println("调整后 :" + i + Arrays.toString(array));
			
			System.out.println();
		}
		
	}
	
	/**
	 * 构建最大堆
	 * @param array
	 */
	private static void buildMaxHeap(int[] array){
		for(int i = array.length - 1; i > -1; i--){
			adjust(array, array.length, i);
		}
		System.out.println("最大堆初始化为: "+ Arrays.toString(array));
	}
	
	/**
	 * 调整堆
	 * @param array
	 * @param size
	 * @param parent
	 */
	private static void adjust(int[] array, int size, int parent){

			int left = getleftChild(parent);
			int right = getRightChild(parent);
			int large = parent;
			
			if(left < size && array[left] > array[large]){
				large = left;
			}
			
			if(right < size && array[right] > array[large]){
				large = right;
			}
			
			if(large != parent){
				int temp = array[parent];
				array[parent] = array[large];
				array[large] = temp;
				
				adjust(array, size, large);
			}
			
	}
	
	
	/**
	 * 移位 + 1
	 * @param parent
	 * @return
	 */
	private static int getleftChild(int parent){
		return parent * 2 + 1;
	}
	private static int getRightChild(int parent){
		return parent  * 2  + 2;
	}