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

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

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

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

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

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

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

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

建議不明白的同學(xué)觀看視頻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];  //將堆頂元素和堆底元素交換，即得到當(dāng)前最大元素正確的排序位置
            array[0] = array[i];
            array[i] = temp;
            adjustHeap1(array, 0, i);  //整理，將剩余的元素整理成大頂堆
        }
    }

    //自下而上構(gòu)建大頂堆：將array看成完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)
    private static int[] buildMaxHeap(int[] array) {
        //從最后一個(gè)節(jié)點(diǎn)array.length-1的父節(jié)點(diǎn)（array.length-1-1）/2開(kāi)始，直到根節(jié)點(diǎn)0，反復(fù)調(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é)點(diǎn)
        for (int i = 2*k+1; i <= length - 1; i = 2*i+1) {    //i為初始化為節(jié)點(diǎn)k的左孩子，沿節(jié)點(diǎn)較大的子節(jié)點(diǎn)向下調(diào)整

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

    //自上而下調(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é)點(diǎn)中較大節(jié)點(diǎn)交換
            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));
    }
}

堆排序時(shí)間計(jì)算分兩部分，構(gòu)建堆時(shí)間復(fù)雜度O(n)，調(diào)整堆時(shí)間復(fù)雜度O(nlogn)，總的時(shí)間復(fù)雜度O(nlogn)，堆排序?yàn)榫偷嘏判?，空間復(fù)雜度O(1)。