排序算法Java代码实现（六）—— 堆排序

本片内容：

• 堆排序

 堆排序

最大堆：

　　二叉堆是完全二叉树或者是近似完全二叉树，

　　当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。（父节点大于任何一个子节点）

算法思想：

1. 把n个元素建立最大堆，把堆顶元素a[0]与待排序序列的最后一个数据a[n-1]交换；
2. 把剩下的n-1个元素重新建立最大堆，把堆顶元素a[0]与待排序序列的最后一个元素a[n-2]交换；
3. 把剩下的n-2个元素重新建立最大堆，把堆顶元素a[0]与待排序序列的最后一个元素a[n-3]交换；

重复以上步骤，直到把最后两个元素建成最大堆并进行交换，得到的序列就是排序后的有序序列。

代码实现：

/**
 * 
 */
package com.cherish.sortingalgorithm;

/**
 * @author acer
 *
 */
public class chapter_7_堆排序 extends arraybase {

    /**
     * @param args
     */
    public static void main(string[] args) {
        // todo 自动生成的方法存根
        int[] array = new int[] {3,4,7,9,2,5,1,8,6};
        heapsorting(array);
        printarray(array);

    }
    
    //堆排序
    public static void heapsorting(int[] array)
    {
        int arraylength = array.length;
        //循环建堆
        for(int i = 0;i < arraylength-1;i++) 
        {
            //建堆，建一次最大堆，寻找一个待排序列的最大数
            buildmaxheap(array,arraylength-1-i);
            //交换堆顶元素（带排序序列的最大数）和最后一个元素  array[0]是堆顶
            swap(array,0,arraylength-1-i);
            
        }
    }
    
    //建最大堆
    public static void buildmaxheap(int[] array,int lastindex)
    {
        //从最后一个节点（index）的父节点开始
        for(int i = (lastindex-1)/2 ; i >= 0; i--)
        {
            //k 保存正在判断的节点
            int k = i;
            //如果当前k节点的子节点存在
            while(k*2+1 <= lastindex)
            {
                //k节点的左子节点的索引
                int biggerindex = 2*k + 1;
                //如果k节点的左子节点biggerindex小于index,即biggerindex+1代表的k节点的右子节点存在
                if(biggerindex < lastindex)
                {
                    //若右子节点的值较大
                    if(array[biggerindex]<array[biggerindex + 1])
                    {
                        //biggerindex总是记录较大子节点的索引
                        biggerindex = biggerindex + 1;
                    }
                }
                //如果k节点的值小于其较大的子节点的值，交换他们
                if(array[k] < array[biggerindex])
                {
                    swap(array,k,biggerindex);
                    //将biggerindex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    k = biggerindex;
                }else
                {
                    //当前判断节点k(父节点)大于他的两个子节点时，跳出while循环
                    break;
                }
                
            }
        }
    }
}

 

实现结果：

 

 由上图可以看到，每次建立最大堆时，最大的数都在array[0],下一次建堆时，上一个最大的数已经移到数组尾部了。