堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法最盅。堆是一個近似完全二叉樹的結(jié)構(gòu)态辛，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點潜叛。

描述：

1絮爷、用數(shù)組創(chuàng)建一個最大堆（子結(jié)點的鍵值或索引總是小于它的父節(jié)點），如果二叉樹中父節(jié)點比子節(jié)點小欢峰，則交換位置葬荷，注意交換后下面的子樹規(guī)則可能被破壞，所以要循環(huán)至葉子節(jié)點。
2、此時數(shù)組中的第一個元素就是最大堆的根節(jié)點磨澡，也就是最大的元素。
2扒吁、將最大堆的根節(jié)點取出和最后一個元素交換，放在數(shù)組最后室囊，剩下的元素繼續(xù)創(chuàng)建最大堆雕崩，重復(fù)至排序完成。

動畫：

堆排序.gif

代碼：

    private void heapSort(int[] array) {
        //先創(chuàng)建最大堆
        int length = array.length;
        //length / 2 - 1是完全二叉樹最后一個非葉子節(jié)點
        //從最后一個非葉子節(jié)點開始整理融撞，直到根節(jié)點（下標0）
        for (int i = length / 2 - 1; i >= 0; i--) {
            maxHeapify(array, i, length - 1);
        }
        for (int i = length - 1; i > 0; i--) {
            //下標為0的元素為根節(jié)點且最大盼铁，取出放到最后
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //剩下的繼續(xù)整理
            maxHeapify(array, 0, i - 1);
        }
    }

    /**
     * 整理最大堆
     * @param array 數(shù)組
     * @param start 起點下標
     * @param end 最后一個葉子節(jié)點下標
     */
    private void maxHeapify(int[] array, int start, int end) {
        int parent = start;
        //左孩子下標是父節(jié)點的2倍加1
        int child = parent * 2 + 1;
        while (child <= end) {
            //child + 1 表示右孩子
            //如果有右孩子 且 左孩子小于右孩子  則記錄大的那個（這里加=號是保證排序穩(wěn)定）
            if (child + 1 <= end && array[child] <= array[child + 1]) {
                child++;
            }
            if (array[parent] > array[child]) {
                return;
            } else {
                //交換父子節(jié)點
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                //繼續(xù)將子節(jié)點作為父節(jié)點整理
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }