排序算法之堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。它是选择排序的一种，可以利用数组的特点，快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。在本次的排序算法当中使用的时大根堆的性质（最大堆性质），即每个子结点的元素的值都不能大于其父结点的元素的值。

什么是完全二叉树？它的定义是：若二叉树深为h，除第h层外，其他各层(1~h-1)的结点数都达到最大个数，第h层所有的几点都连续集中在最左边。

排序思想

从我们拿到一个无序的序列开始说起。拿到一个序列之后，要使用堆排序的话，我们当然首先要构建一个堆。在构建堆的过程当中我们要维护堆的最大堆性质，一边构建一边维护的话，当堆建好我们也已经维护好了。最后，就需要从堆里取出元素进行排序即可。

堆排序三部曲

下面我们将上面三个部分逐一进行分析，从最简单的开始。这里，先做出一点定义，将上述的三个部分分别用一个函数（方法）来实现，命名如下：

从堆中取出元素完成排序

假设我们现在已经得到了一个堆，它维持着最大堆的性质。所以，我们可以推出：整个序列当中最大的元素必然是在二叉树的根节点处。为了排成有序列（这里按照非降序进行排列），第一步应该是：将这个元素放到序列的最后（这里打算直接在原数组当中进行排序，节省不必要的空间开销），并在树中(堆中)除去这个结点。最大元素放在数组最后了，那么数组原本的最后一个元素就应该去到了二叉树的根结点处。此时，最大堆的性质可能被打乱了。所以，第二步：需要对根节点执行维护最大堆的操作；

也就是说排序的函数（方法）的具体代码实现应该是这样的：

维护最大堆性质

下面讨论怎么实现对任意节点(不局限于根节点，如果需要只对根节点进行维护，提供一个参数(根节点的下标)即可)实行最大堆性质的维护。原理应该是这样的：对于给出的结点，取出它的值，然后和它的子结点的值进行比较。若不存在比它大的值，则不需要进行任何操作；若存在比它大的值，将它和大的值换个位置。然后对换了位置的地方，重复上述的步骤(递归调用)即可完成。实现代码如下所示：

//array是待排序的序列，i是任意节点的下标
//其中出现的heap_size是堆的有效长度的全局变量
heap_keep_max(int[] array, int i){
	//定义两个变量代表二叉树的孩子节点的下标
	int l,r;
	int largest,tmp;
	//以0下标为第一个元素（根节点）
	l = 2 * i + 1;
	r = l + 1;
	//判断i的左孩子节点是否比array[i]大
	if (l <= array.heap_size && array[l] > array[i]){
		largest = l;
	}else{
		largest = i;
	}
	//判断i的右孩子节点是否比array[largest]大
	if (r <= array.heap_size && array[r] >= array[largest]){
		largest = r;
	}
	//判断是否需要进行两数的呼唤
	if (largest != i){
		//开始进行交换
		exchange(array[i],array[largest]);
		//交换后可能破坏了最大堆性质，维护进行了交换的地方
		heap_keep_max(array,largest);
	}
}

构建堆

我们如果假设l和r为某一个节点i的左孩子和右孩子。在第一个节点(根节点)的下标设置为0的情况下，通过一些数学关系，我们可以得出两个关系式l = 2 * i + 1,r = l + 1。构建堆的时候，很显然我们从底部往上构建比从上往下构建要容易得多，因为你不知道最大的数会出现在什么地方。所以，我们取待排序列的最后一个数开始。一边维护最大堆的性质一边构建堆。具体的代码如下所示：

HeapBuild(int[] array){
	heap_size = array.length;
	for (int i = array.length-1; i >= 0; i--){
		HeapKeepMax(array,i);
	}
}

具体实现

上面给出了初步的逻辑代码，下面给出在Java环境下运行通过的详细代码：

package heap;
/**
 * 堆排序
 * @author ERIC_LAI
 */
public class Heap {
    private static int heap_size;

    public static void main(String[] args) {
        int [] array = {4,1,3,2,16,9,10,14,8,7};
        Heap.heap_build(array);
        Heap.heap_sort(array);       
       System.out.print("final: ");
        for (int j = 0; j < array.length; j++) {
            System.out.print(array[j]+" ");
        }
    }
    
    /**
     * 维护最大堆性质
     * @param array 待排序列的首地址
     * @param i 需要维护的下标
     */
    public static void heap_keep_max(int[] array, int i){
        int largest = 0;
        int tmp = 0;
        int l = 2*i + 1;
        int r = 2*i + 2;
        //将array[i]与左孩子相比,如果大于左孩子则保持不变,
        //否则比这个数大的数的下标放到large当中
        if (l <= heap_size-1 && array[l] > array[i]){
            largest = l;
        }else{
            largest = i;
        }
        //将和左孩子比完之后大的和右孩子比,将大的数字的下标放在large当中
        if (r <= heap_size-1 && array[r] > array[largest]){
            largest = r;
        }
        //如果最大的数不在结点上则开始调换
        if (largest != i){
            tmp = array[i];
            array[i] = array[largest];
            array[largest] = tmp;
            Heap.heap_keep_max(array, largest);
        }
    }
    
    /**
     * 构建堆
     * @param array 待排序列的首地址
     */
    public static void heap_build(int[] array){
        heap_size = array.length;
        for (int i = array.length/2 - 1;i >= 0; i--){
            Heap.heap_keep_max(array, i);
		 //这里的注释部分用于显示每次维护后的结果，方便调试
//          System.out.print("i="+i);
//          for (int j = 0; j < array.length; j++) {
//              System.out.print(" "+array[j]+" ");
//            }
//          System.out.println();
        }
    }

	/**
     * 排序
     * @param array 待排序列的首地址
     */
    private static void heap_sort(int[] array) {
        for (int k = array.length-1 ;k > 0; k--){
            int tmp;
            tmp = array[k];
            array[k] = array[0];
            array[0] = tmp;
            heap_size = heap_size - 1;
            Heap.heap_keep_max(array, 0);
        }
    }
}

什么是堆排序

排序思想

堆排序三部曲

从堆中取出元素完成排序

维护最大堆性质

构建堆

具体实现