摘要：一堆排序介紹來(lái)源百度百科堆排序是指利用堆積樹(shù)堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。

來(lái)源百度百科：

堆排序(Heapsort)是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹(shù)。

前面我已經(jīng)有二叉樹(shù)入門的文章了，當(dāng)時(shí)講解的是二叉查找樹(shù)，那上面所說(shuō)的完全二叉樹(shù)是怎么樣的一種二叉樹(shù)呢？？還有滿二叉樹(shù)又是怎么的一種二叉樹(shù)呢？？甚至還有完滿二叉樹(shù)？？

完全二叉樹(shù)： 除了最后一層之外的其他每一層都被完全填充，并且所有結(jié)點(diǎn)都保持向左對(duì)齊。

滿二叉樹(shù)：除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，每一層(當(dāng)然包含最后一層)都被完全填充。

完滿二叉樹(shù)：除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)。

下面用圖來(lái)說(shuō)話：

完全二叉樹(shù)(Complete Binary Tree)：

滿二叉樹(shù)(Perfect Binary Tree)：

完滿二叉樹(shù)(Full Binary Tree)：

參考資料：

http://www.cnblogs.com/idorax/p/6441043.html

簡(jiǎn)單來(lái)說(shuō)：堆排序是將數(shù)據(jù)看成是完全二叉樹(shù)、根據(jù)完全二叉樹(shù)的特性來(lái)進(jìn)行排序的一種算法

最大堆要求節(jié)點(diǎn)的元素都要不小于其孩子，最小堆要求節(jié)點(diǎn)元素都不大于其左右孩子

那么處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值

這里我們討論最大堆：當(dāng)前每個(gè)父節(jié)點(diǎn)都大于子節(jié)點(diǎn)

完全二叉樹(shù)有個(gè)特性：左邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍 + 1，右邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍 + 2

現(xiàn)在我們有一個(gè)完全二叉樹(shù)：左子樹(shù)和右子樹(shù)都符合最大堆-->父>子

但是我們會(huì)發(fā)現(xiàn)：根元素所在的數(shù)并不符合，明顯的是：1是小于7的

我們就對(duì)其進(jìn)行交換，交換完之后我們會(huì)發(fā)現(xiàn)：右子樹(shù)又不符合了～

因?yàn)?，右子?shù)變成了這樣：

最后，我們將右子數(shù)的最大值也交換到右子樹(shù)的根元素上

于是我們第一次的建堆操作就完成了！

可以發(fā)現(xiàn)的是：一次堆建立完之后，我們的最大值就在了堆的根節(jié)點(diǎn)上

隨后將堆頂最大值和數(shù)組最后的元素進(jìn)行替換，我們就完成了一趟排序了。

接下來(lái)，剩下的數(shù)不斷進(jìn)行建堆，交換就可以完成我們的堆排序了

.........建堆，交換....建堆，交換...建堆，交換...建堆，交換..

比較當(dāng)前父節(jié)點(diǎn)是否大于子節(jié)點(diǎn)，如果大于就交換，直到一趟建堆完成～

    /**
     * 建堆
     *
     * @param arrays          看作是完全二叉樹(shù)
     * @param currentRootNode 當(dāng)前父節(jié)點(diǎn)位置
     * @param size            節(jié)點(diǎn)總數(shù)
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {

        if (currentRootNode < size) {
            //左子樹(shù)和右字?jǐn)?shù)的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;

            //把當(dāng)前父節(jié)點(diǎn)位置看成是最大的
            int max = currentRootNode;

            if (left < size) {
                //如果比當(dāng)前根元素要大，記錄它的位置
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //如果比當(dāng)前根元素要大，記錄它的位置
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //如果最大的不是根元素位置，那么就交換
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;

                //繼續(xù)比較，直到完成一次建堆
                heapify(arrays, max, size);
            }
        }
    }

值得注意的是：在上面體驗(yàn)堆排序時(shí)，我們是左子樹(shù)和右子數(shù)都是已經(jīng)有父>子這么一個(gè)條件的了。

顯然，一個(gè)普通的數(shù)組并不能有這種條件(父>子)，因此，我們往往是從數(shù)組最后一個(gè)元素來(lái)進(jìn)行建堆

    /**
     * 完成一次建堆，最大值在堆的頂部(根節(jié)點(diǎn))
     */
    public static void maxHeapify(int[] arrays, int size) {

        // 從數(shù)組的尾部開(kāi)始，直到第一個(gè)元素(角標(biāo)為0)
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }

    }

完成第一次建堆之后，我們會(huì)發(fā)現(xiàn)最大值會(huì)在數(shù)組的首位：

接下來(lái)不斷建堆，然后讓數(shù)組最后一位與當(dāng)前堆頂(數(shù)組第一位)進(jìn)行交換即可排序：

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

        //每次建堆就可以排除一個(gè)元素了
        maxHeapify(arrays, arrays.length - i);

        //交換
        int temp = arrays[0];
        arrays[0] = arrays[(arrays.length - 1) - i];
        arrays[(arrays.length - 1) - i] = temp;

    }

堆排序是比其他排序要難一點(diǎn)，他用到了完全二叉樹(shù)這么一個(gè)特性來(lái)進(jìn)行排序，代碼實(shí)現(xiàn)上也比其他排序要復(fù)雜一點(diǎn)。

參考資料：

http://www.cnblogs.com/skywang12345/p/3602162.html

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y