上一篇完成了堆的建立。在此基础上就可以实现堆排序。

思路：在此我们以实现从小到大排序为例。通过第一次的堆建立，生成的大顶堆的根结点值是最大值。然后我们将这个值放到某个地方可以不管它了（实际操作时都是放到整个堆的最后面，然后把最后面那个结点值放到最顶端），此时我们需要操作的元素个数已经少了一个，把剩下的元素再做一个建堆的操作（其实就是堆顶根结点元素的一个交换排列，其他节点的元素是之前已经排列好了的）。依次这个流程到最后。

注意：如果要做一个从大到小的排序，那么需要建立一个小顶堆，即最上面的元素是最小的。然后再堆排序的过程中会把最小的元素放到最后面，这样就实现了一个从大到小的排序。反之，从小到大排序，也是一样的道理。

下面看java实现的代码。综合了堆建立的代码。

package test;/** *  @author hushunfeng *   *  大顶堆堆排序 *  从小到大排序 *   */public class HeapSort {    public static void main(String[] args) {        int[] array = {10,20,30,40,50,60,70,80};        //调整堆        int temp = 0;        for(int j=7;j>=0;j--) {            createHeap(array,j+1);            temp = array[0];            array[0] = array[j];            array[j] = temp;        }        for(int i=0;i<8;i++) {            System.out.println(array[i]);        }    }        /**     * 将无序序列进行建堆     * @param array 要建的堆     */private static void createHeap(int[] array,int heapNum) {        //heapNum = array.length;        //根据建堆过程，先从第n/2个元素开始        //它是最后一个非终端结点        for(int i = heapNum/2-1; i >= 0; i--) {            adjustNode(array,i,heapNum);        }    }        /**     *      * 将parentNode为根结点的子树调整成一个最大堆     * @param array 要调整的无序序列，以数组的形式进行存储     * @param parentNode  以此结点为根结点建立子树     *      */    //由于我们采用的是大顶堆,父结点要调整成大于子结点    private static void adjustNode(int[] array,int parentNode,int nodeNum) {                //数组长度    //    int arrayNum = array.length;        //跳动的父结点游标(在子树层数大于2层时适用)        int parentIndex = parentNode;        //左子结点        int childLeftNode = 2*parentIndex+1;        //右子结点        int childRightNode = 2*parentIndex+2;        //        int maxNode;                //将可能要跳动的父结点的数据缓存起来        int temp = array[parentNode];                //不断地跳动父结点的游标        //防止右子结点不存在这种情况，不然会内存溢出        while(childLeftNode
     
      array[childRightNode])                    maxNode = childLeftNode;                else                     maxNode = childRightNode;            }                        //比较，交换位置            if(array[parentIndex]
     

注：相比堆建立中，程序稍微进行了优化和修改。

修改后的第二版，考虑到从第二次建堆开始只需对根结点进行调整。

package test;/** *  @author hushunfeng *   *  大顶堆堆排序 *  从小到大排序 *   */public class HeapSort {    public static void main(String[] args) {        int[] array = {10,20,30,40,50,60,70,80};        //先新建一个堆        createNewHeap(array);        //去除最后一个元素，将根结点进行重新调整        int temp = 0;        for(int j=7;j>=0;j--) {            temp = array[0];            array[0] = array[j];            array[j] = temp;            adjustNode(array,0,j);        }        for(int i=0;i<8;i++) {            System.out.println(array[i]);        }    }        /**     * 将无序序列进行建堆     * @param array 要建的堆     */private static void createNewHeap(int[] array) {        int heapNum = array.length;        //根据建堆过程，先从第n/2个元素开始        //它是最后一个非终端结点        for(int i = heapNum/2-1; i >= 0; i--) {            adjustNode(array,i,heapNum);        }    }        /**     *      * 将parentNode为根结点的子树调整成一个最大堆     * @param array 要调整的无序序列，以数组的形式进行存储     * @param parentNode  以此结点为根结点建立子树     *      */    //由于我们采用的是大顶堆,父结点要调整成大于子结点    private static void adjustNode(int[] array,int parentNode,int nodeNum) {                //数组长度    //    int arrayNum = array.length;        //跳动的父结点游标(在子树层数大于2层时适用)        int parentIndex = parentNode;        //左子结点        int childLeftNode = 2*parentIndex+1;        //右子结点        int childRightNode = 2*parentIndex+2;        //        int maxNode;                //将可能要跳动的父结点的数据缓存起来        int temp = array[parentNode];                //不断地跳动父结点的游标        //防止右子结点不存在这种情况，不然会内存溢出        while(childLeftNode
     
      array[childRightNode])                    maxNode = childLeftNode;                else                     maxNode = childRightNode;            }                        //比较，交换位置            if(array[parentIndex]