学步园

堆排序的基本思想：将array[n]的数组看成一棵完全二叉树。父节点均大于其左右子节点的，为大根堆；父节点均小于其左右子节点的，为小根堆。

1) 初建堆--从length/2节点开始，自底向上调整，使array[n]成为一个大顶堆；

2) 交换堆顶元素（最大值）和最后一个元素，将移走最大元素后的剩余元素，从堆顶开始再调整为堆；

3) 重复步骤2)n-1次，则实现array[n]升序排列。

堆调整过程：

1) 从待调整元素i开始开始调整，自顶向下地作如下调整：

2) 将待调整元素与其左右孩子节点比较，三者中最大者作为新的父节点；

3) 若2)中存在元素交换，则将交换后的孩子节点作为待调整节点，转向第2)步；否则，结束调整。

//调整堆<br /> void HeapAdjust( int array[], int i, int length )<br /> {<br /> int nChild, nTemp;<br /> for( nTemp = array[i]; i*2+1 < length; i = nChild )<br /> {<br /> nChild = i*2+1; //子节点 = 父节点*2 + 1<br /> if( nChild < length-1 && array[nChild] < array[nChild+1] )<br /> nChild++; //比较出两个子节点的较大者nChild<br /> if ( nTemp < array[nChild] ) //如果待调整节点 < 子节点的较大者<br /> {<br /> array[i] = array[nChild]; //将子节点较大者上移，作为新的父节点<br /> }<br /> else break; //否则退出循环，结束本次调整<br /> array[nChild] = nTemp;<br /> }<br /> }<br /> void HeapSort( int array[], int length)<br /> {<br /> int i;<br /> //初建堆<br /> for ( i = length/2-1; i>=0; --i )<br /> {<br /> HeapAdjust( array, i, length );<br /> }<br /> for ( i = length-1; i>0; --i )<br /> {<br /> swap( array[0], array[i] ); //交换堆顶元素和最后一个元素<br /> HeapAdjust( array, 0, i ); //从堆顶元素开始重调整堆，新的长度为i<br /> }<br /> }