2012/3/28----堆排序

堆排序是一种基于二叉树的排序，利用二叉树的性质进行排序的算法。但是这里的二叉树并不是真实存在的，是我们利用数组的编号进行设计的特殊的二叉树。

而堆排序其本质是一个就地排序算法。

/*
 * 堆排序算法
 * @version 1.0 2012/3/28
 * @author akon
 */
package com.akon405.www;

public class HeapSort {
	/*
	 * createMaxHeap的功能：
	 * 创建最大堆
	 */
	public void createMaxHeap(int[] A,int length){
		int j;//最后一个非叶子节点		
		for(j=length/2-1;j>=0;j--){
			heapAdjust(A,j,length);//依次遍历每个非叶结点，然后做出调整
		}
	}
	/*
	 * heapAdjust的功能：
	 * 进行堆的调整，使它始终是最大堆
	 */
	public void heapAdjust(int[] A,int i,int length){
		int l,r,temp;
		l=i*2+1;//非叶节点的左子节点
		r=i*2+2;//非叶节点的右子节点

		int largest=i;//比较当前节点和子节点的大小的标志
		
		while(l<length||r<length){
			if(l<length&&r<length){
				//当左右子节点都存在的时候
				if(A[i]<A[l]&&A[r]<A[l]){
					largest=l;
				}
				if(A[i]<A[r]&&A[r]>A[l]){
					largest=r;
				}
			}else if(l<length&&r>=length){
				//只有左子节点，没有右子节点
				if(A[i]<A[l]){
					largest=l;
				}
			}
		if(largest!=i){
			temp=A[i];
			A[i]=A[largest];
			A[largest]=temp;
			
			i=largest;
			l=i*2+1;
			r=i*2+2;
		}else{
			break;
		}
		}
	}
	/*
	 * HeapSort的功能：
	 * 进行堆排序
	 */
	public  HeapSort(int[] A,int length){
		
		int temp;
		createMaxHeap(A,length);//创建最大堆
		System.out.print("最大堆：");
		for(int i=0;i<A.length;i++){
			System.out.print(A[i]+",");//输出我们第一次创建的最大堆（主要是用来调试程序）
			}
		while(length>1){
			temp=A[length-1];
			A[length-1]=A[0];
			A[0]=temp;
			length--; //把最大的数值放到数组末尾，然后再把堆进行整理，让剩余的数值继续构成一个最大堆
			heapAdjust(A,0,length);
		}
		System.out.println("");
		System.out.print("排序结果：");
		for(int i=0;i<A.length;i++)
			System.out.print(A[i]+",");
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={40,10,32,8,78,98,20,3,1};
		int length=A.length;
		new HeapSort(A,length);
	}
}