堆排序

堆排序主要分两个主要步骤：1、建立最大（最小）堆；2、调整堆。

文中主要给出算法，有详细注释，注意由于计算方便，该算法下表为0的数组不能进行排序。

package org.mino.sort;

/**
 * 堆排序
 * @author DingJie
 */
public class HeapSort {  
    public static void main(String[] args) {  
        // 数组0下标元素作为暂存单元  
    	int []array = { 45, 12, 11, 32, 56, 11, 8, 30, 3 };  
    	System.out.println("排序前:");
        for (int i = 1; i < array.length; i++) {  
            System.out.print(array[i] + " ");  
        }
        System.out.println("");
        heapSort(array);  
        System.out.println("排序后:");
        for (int i = 1; i < array.length; i++) {  
            System.out.print(array[i] + " ");  
        }  
    }  
  
    /**
     * 堆排序
     * @param array
     */
    public static void heapSort(int[] array) {  
        // 对数组进行筛选，建成一个大顶堆  
        double len = array.length - 1;  
        for (int i = (int) Math.floor(len / 2); i > 0; i--) { //第一个不排序
            heapAdjust(array, i, array.length - 1);  
        }  
        System.out.println("排序中：");
        for(int i = 1; i < array.length;i++) {
        	System.out.print(array[i] + " ");
        }
        System.out.println("");
        for (int i = array.length - 1; i > 1; i--) {  
            // 将堆顶元素与最后一个元素调换位置，即输出最大值 ,也可输出第i大的值【逆序复制就行】
            swap(array, 1, i);  
            // 将最后一位剔出，数组最大下标变为i-1。自队顶至叶子进行调整，形成一个新堆，此过程称为筛选  
            heapAdjust(array, 1, i - 1);  
        }  
    }  
  
    /**
     * 建堆函数，认为【s，m】中只有 s  
     * 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆
     * @param array
     * @param s
     * @param m
     */
    public static void heapAdjust(int[] array, int s, int m) {  
        // 用0下标元素作为暂存单元  
        array[0] = array[s];  
        // 沿孩子较大的结点向下筛选  
        for (int j = 2 * s; j <= m; j *= 2) {       //*=2递归查看孩子
            // 保证j为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界  
            if (j < m && array[j] < array[j + 1]) { //选出最大的一个 
                j++;  
            }  
            if (!(array[0] < array[j])) {           //已经是最大堆不需要递归
                break;  
            }  
            // 若S位较小，应将较大孩子上移  
            array[s] = array[j];  
            // 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选  
            s = j;  							   //S指向刚上移的元素位置
        }//end_for  
        // 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。  
        array[s] = array[0];  
    }  
      
    /**
     * 交换函数
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {  
        int temp;  
        temp = array[i];  
        array[i] = array[j];  
        array[j] = temp;  
    }  
}