摘要：很早就學習了堆排序但當時沒有用代碼實現(xiàn)，現(xiàn)在再去想實現(xiàn)已經(jīng)忘光光啦，于是就去網(wǎng)上搜了一番，發(fā)現(xiàn)沒有一篇我能認真看完的文章，沒辦法就是沒耐心，就是笨唄。。。

很早就學習了堆排序但當時沒有用代碼實現(xiàn)，現(xiàn)在再去想實現(xiàn)已經(jīng)忘光光啦┑(￣Д ￣)┍，于是就去網(wǎng)上搜了一番，發(fā)現(xiàn)沒有一篇我能認真看完的文章，沒辦法就是沒耐心，就是笨唄。。。好了，言歸正傳=￣ω￣=

首先明白什么是堆，什么是完全二叉樹，什么是大頂堆，相信百度一下很容易理解o(^▽^)o。

堆可以用數(shù)組來存儲，如下圖，數(shù)組 a[0，...，9] 表示一個堆在數(shù)組中的存儲模式。數(shù)組中下標為i的節(jié)點的子節(jié)點下標分別為2*i+1、2*i+2，下標為j的子節(jié)點的父節(jié)點下標為(j-1)/2。

將待排序數(shù)組構(gòu)建成一個大頂堆，也就是變換原始數(shù)組中元素的位置，使之滿足大頂堆的定義。

將堆頂節(jié)點與堆中末尾節(jié)點交換，也就是數(shù)組的首尾元素交換，此時末尾節(jié)點已為最大元素，考慮剩余節(jié)點形成的堆。

將最新的堆重新構(gòu)造成大頂堆。

重復第2步、第3步直到堆中節(jié)點全部輸出。

建議不明白的同學觀看視頻https://www.bilibili.com/vide...

public class HeapSort {

    public static void heapSort(int[] array) {
        array = buildMaxHeap(array); //初始建堆，array[0]為第一趟值最大的元素
        for (int i = array.length - 1; i >= 1; i--) {
            int temp = array[0];  //將堆頂元素和堆底元素交換，即得到當前最大元素正確的排序位置
            array[0] = array[i];
            array[i] = temp;
            adjustHeap1(array, 0, i);  //整理，將剩余的元素整理成大頂堆
        }
    }

    //自下而上構(gòu)建大頂堆：將array看成完全二叉樹的順序存儲結(jié)構(gòu)
    private static int[] buildMaxHeap(int[] array) {
        //從最后一個節(jié)點array.length-1的父節(jié)點（array.length-1-1）/2開始，直到根節(jié)點0，反復調(diào)整堆
        for(int i=(array.length-2)/2;i>=0;i--){
            adjustHeap1(array, i, array.length);
        }
        return array;

    }

    //自上而下調(diào)整大頂堆（非遞歸）
    private static void adjustHeap1(int[] array, int k, int length) {
        int temp = array[k]; //堆頂節(jié)點
        for (int i = 2*k+1; i <= length - 1; i = 2*i+1) {    //i為初始化為節(jié)點k的左孩子，沿節(jié)點較大的子節(jié)點向下調(diào)整

            if (i+1< length && array[i] < array[i + 1]) {  //如果左孩子小于右孩子
                i++;   //則取右孩子節(jié)點的下標
            }
            if (temp >= array[i]) {  //堆頂節(jié)點 >=左右孩子中較大者，調(diào)整結(jié)束
                break;
            } else {   //根節(jié)點 < 左右子女中關(guān)鍵字較大者
                array[k] = array[i];  //將左右子結(jié)點中較大值array[i]調(diào)整到雙親節(jié)點上
                k = i; //【關(guān)鍵】修改k值，以便繼續(xù)向下調(diào)整
            }
        }
        array[k] = temp;  //被堆頂結(jié)點的值放人最終位置
        
    }

    //自上而下調(diào)整大頂堆（遞歸）
    private static void adjustHeap2(int[] array, int k, int length) {
        int k1=2*k+1;  
        if(k1length-1||array[k]>=array[k1]){
            return;
        }else{
            int temp = array[k];  //將堆頂元素和左右子結(jié)點中較大節(jié)點交換
            array[k] = array[k1];
            array[k1] = temp;
            adjustHeap2(array,k1,length);
        }
    }
    
    

    public static void main(String[] args) {
        int[] a = {87,45,78,32,17,65,53,9,122,133};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}

堆排序時間計算分兩部分，構(gòu)建堆時間復雜度O(n)，調(diào)整堆時間復雜度O(nlogn)，總的時間復雜度O(nlogn)，堆排序為就地排序，空間復雜度O(1)。