堆排序
????首先堆排序分為兩個過程，建堆和調(diào)整堆，其中建堆過程中也要用到調(diào)整堆，堆排序本質(zhì)上是一個選擇排序，是一個不穩(wěn)定排序。
????堆排序的核心是調(diào)整堆，每次調(diào)整從最后一個葉節(jié)點的父節(jié)點開始，每次拿父節(jié)點和其左右子節(jié)點比較，將子節(jié)點中比較大的節(jié)點和父節(jié)點進行交換，然后節(jié)點依次遞增，像這樣從下往上進行調(diào)整；一次調(diào)整結(jié)束后，此時堆頂元素為最大值，將堆頂元素與最后一個元素進行交換，重新開始調(diào)整。
????首先要找到調(diào)整的起點，也就是最后一個葉子節(jié)點的父親節(jié)點，為(array.length-2)/2，比如數(shù)組長度為7，其最后一個葉子節(jié)點的父親節(jié)點為(7-2)/2=2（下標從0開始）；

時間復(fù)雜度
????堆排序是一種選擇排序，整體主要由構(gòu)建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成。其中構(gòu)建初始堆經(jīng)推導復(fù)雜度為O(n)，在交換并重建堆的過程中，需交換n-1次，而重建堆的過程中，根據(jù)完全二叉樹的性質(zhì)，[log2(n-1),log2(n-2)...1]逐步遞減，近似為nlogn。所以堆排序時間復(fù)雜度一般認為就是O(nlogn)級。

public class HeapSort {
    /**
     *
     * @param array 數(shù)組元素
     * @param k  父節(jié)點下標
     * @param length
     */
    public static void adjust(int[] array,int k,int length){
        //父節(jié)點
        int temp=array[k];
        for (int i=2*k;i<length;i=2*i){
           // System.out.println("Parent"+array[k]);
            //調(diào)整
            if(i<length&&array[i]<array[i+1]){
                //找到子節(jié)點大的下標
                i++;
            }
            //如果父節(jié)點比子節(jié)點大，退出
            if (temp>=array[i]){
                break;
            }
            //將子節(jié)點大的元素上移
            array[k]=array[i];
            k=i;
        }
        array[k]=temp;
    }
    /**
     *  建立一個大根堆
     * @param array
     * @return
     */
    public static int [] buildHeap(int [] array){
        for (int i=(array.length-2)/2;i>=0;i--){
            adjust(array,i,array.length-1);
        }
        return array;
    }

    /**
     * 排序算法
     * @param array
     * @return
     */
    public static int [] HeapSort(int [] array){
        //建立大根堆
        array=buildHeap(array);
        for(int i=array.length-1; i>0; i--){
            //將堆頂元素與最后一個元素交換
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //進行調(diào)整
            adjust(array,0,i-1);
        }
        return array;
    }

    public static void main(String[] args) {
        int [] array={10,0,7, 5,4, 6, 3, 2, 1};
       HeapSort(array);
        //buildMaxHeap(array);
        for (int i:array){
            System.out.print(i);
        }
    }
}