堆排序：
一棵完全二叉树，如果父节点的值大于等于左右节点的值，则称此完全二叉树为小根堆（小顶堆）；如果父节点的值小于等于左右节点的值，则次完全二叉树为大根堆（大顶堆）。

堆排序是建立在大顶堆或小顶堆的基础上的，通过不断的交换堆顶元素和堆尾元素，来对数组排序。基于大顶堆的堆排序，数组排序结果是升序的。基于小顶堆的堆排序，数组排序结果是降序的。

流程：
（1）建立堆 （注意调整的顺序是：从右往左，从下往上）
（2）交换堆顶与堆底元素
（3）调整堆（注意调整的顺序是：从0开始）

代码：

public class DuiPaiXu {

    //堆排序

    public  static void heapSort(int[] array) {

        if(array == null || array.length <=1 ) {

            return;

        }

        int totalIndex = array.length-1;

        buildHeap(array,totalIndex);

        while(totalIndex > 0) {

            swap(array,0,totalIndex);

            if(--totalIndex == 0) {

                break;

            }

            adjustHeap(array,0, totalIndex);

        }

    }

    //根据数组建立堆

    public static void buildHeap(int[] array,int totalIndex) {
　　//注意这里i是从（totalIndex-1）/2-1开始的，因为我索引值是从0开始的。

        for(int i=(totalIndex-1)/2-1; i>=0; i--) {

            adjustHeap(array,i, totalIndex);

        }

    }

    //调整堆

    public static void adjustHeap(int[] array,int curIndex, int totalIndex) {

        int biggestIndex = curIndex;

        int leftIndex = 2*curIndex +1;

        int rightIndex = 2*curIndex +2;

        if(rightIndex <= totalIndex) {

            if(array[curIndex] <array[leftIndex] || array[curIndex] <array[rightIndex]) {

                biggestIndex = array[leftIndex] > array[rightIndex] ? leftIndex : rightIndex;

            }

        } else if(leftIndex <= totalIndex ) {

            if(array[curIndex] <array[leftIndex]) {

                biggestIndex = leftIndex;

            }

        }

        if(biggestIndex != curIndex) {

            swap(array, curIndex, biggestIndex);

            adjustHeap(array, biggestIndex, totalIndex);

        }

    }

    public static void swap(int[] array,int i1, int i2) {

        int temp = array[i1];

        array[i1] = array[i2];

        array[i2] = temp;

    }

    public static void main(String[] args) {

        int[] array = {1,3,76,34,23,45,85,46,37};

        heapSort(array);

        for(int i=0; i<array.length; i++) {

            System.out.print(array[i] + " ");

        }

    }

}