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 stubint[] A={40,10,32,8,78,98,20,3,1};int length=A.length;new HeapSort(A,length);}}?