排序算法篇（堆排序）

堆是一种特殊的数据结构，是一种完全二叉树，分为大根堆（根节点的值大于孩子节点）和小根堆（根节点小于孩子节点），建堆和堆排序代码如下：

packagecn.com.daydayup.test;

publicclassStackSort{

publicstaticvoidmain(String[]args){

int[]a={26,5,77,1,61,11,59,15,48,19};

Sort(a);

}

//堆排需方法

publicstaticvoidSort(int[]a){

intn=a.length;//取得数组总长度，及堆最大的序号

inttemp=0;

Display(a,"Beforesort:");

//这是建堆的过程，一次从倒数第二层的根节点开始调整堆，即数组下标为i/2开始，一直到顶层根节点，这样就建好堆了。。

for(inti=n/2;i>0;i--){

Adjust(a,i-1,n);//从倒数第二层的最后一个根节点开始调整堆

Display(a,"建立大根堆:");

}

System.out.println("---------------------------------------");

for(inti=n-2;i>=0;i--){//这是堆排序的具体算法，思想是每次取出堆的最顶层根节点，即数组下标为0，然后与最后一个节点即i+1交换，这样对于大根堆而言，最大值总是在后面。。循环过后就能排序了。。

temp=a[i+1];//取出最后一个元素

a[i+1]=a[0];//取出第一个元素，即顶层根节点

a[0]=temp;//交换位置

Adjust(a,0,i+1);//调整堆

Display(a,"重建立大根堆:");

}

Display(a,"Aftersort:");

}

/**

*调整堆的方法

*@parama　要调整的数组，即堆

*@parami　调整的根节点，即起始位置

*@paramn　要调整的终止位置

*/

publicstaticvoidAdjust(int[]a,inti,intn){

intj=0;

inttemp=0;

temp=a[i];//取出根节点

j=2*i+1;//左孩子节点

while(j<=n-1){

if(j<n-1&&a[j]<a[j+1])//比较左右孩子，取出较大的孩子

j++;

if(temp>=a[j])//如果根节点大于孩子节点则退出循环，不用调整

break;

a[(j-1)/2]=a[j];//较大的孩子节点值赋值给根节点

j=2*j+1;//继续寻找左孩子

}

a[(j-1)/2]=temp;//将根节点赋值给最后一个空出来的节点

}

//打印堆内容

publicstaticvoidDisplay(int[]a,Stringstr){

System.out.println(str);

for(inti=0;i<a.length;i++)

System.out.print(a[i]+"");

System.out.println();

}

}