HeapSort

public class HeapSort {
	int heapSize;
	int[] heapArr;
	
	//循环实现堆排序
	public void cycleMaxHeap(int location){
		int left;
		int right;
		int largest;
		while( location <= heapSize){
			left = location*2;
			right = location*2 + 1;
			//左子节点是否大于父节点
			if(left <= heapSize && heapArr[left - 1] > heapArr[location - 1]){
				largest = left;
			}else{
				largest = location;
			}
			//右子节点是否大于新父节点
			if(right <= heapSize && heapArr[right - 1] > heapArr[largest - 1]){
				largest = right;
			}
			if(largest != location){
				int temp = heapArr[location - 1];
				heapArr[location - 1] = heapArr[largest - 1];
				heapArr[largest - 1] = temp;
			}else{
				break;
			}
			location = largest;
		}
	}
	//递归实现堆排序
	public void maxHeap( int location ){
		int left = location*2;
		int right = location*2 + 1;
		int largest;
		//左子节点是否大于父节点
		if(left <= heapSize && heapArr[left - 1] > heapArr[location - 1]){
			largest = left;
		}else{
			largest = location;
		}
		//右子节点是否大于新父节点
		if(right <= heapSize && heapArr[right - 1] > heapArr[largest - 1]){
			largest = right;
		}
		if(largest != location){
			int temp = heapArr[location - 1];
			heapArr[location - 1] = heapArr[largest - 1];
			heapArr[largest - 1] = temp;
		}else{
			return;
		}
		maxHeap(largest);
	}

	public void buildMaxHeap(){
		heapSize = heapArr.length;
		for(int i = heapSize/2; i >= 1; i--){
			cycleMaxHeap(i);
//			maxHeap(i);
		}
	}
	public void heapSort(){
		buildMaxHeap();
		for(int i = heapArr.length; i >= 1; i --){
			int temp = heapArr[i - 1];
			heapArr[i - 1] = heapArr[0];
			heapArr[0] = temp;
			heapSize --;//最后的元素用提取的最大元素填充，不参与堆排
			cycleMaxHeap(1);
//			maxHeap(1);
		}
	}
	//main_test
	public static void main(String[] args) {
		HeapSort hs = new HeapSort();
		int[] tempArr = {15,13,9,5,12,8,7,4,0,6,2,1};
		hs.heapArr = tempArr;
		hs.heapSort();
		for(int i = 0; i < hs.heapArr.length; i ++ )
			System.out.print(hs.heapArr[i] + " ");
	}

}