堆排序就這么簡單

NickZhou 發布于2019-08-19 10:43 / 1285人閱讀

摘要：一堆排序介紹來源百度百科堆排序是指利用堆積樹堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。

一、堆排序介紹

來源百度百科：

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

前面我已經有二叉樹入門的文章了，當時講解的是二叉查找樹，那上面所說的完全二叉樹是怎么樣的一種二叉樹呢？？還有滿二叉樹又是怎么的一種二叉樹呢？？甚至還有完滿二叉樹？？

完全二叉樹：除了最后一層之外的其他每一層都被完全填充，并且所有結點都保持向左對齊。

滿二叉樹：除了葉子結點之外的每一個結點都有兩個孩子，每一層(當然包含最后一層)都被完全填充。

完滿二叉樹：除了葉子結點之外的每一個結點都有兩個孩子結點。

下面用圖來說話：

完全二叉樹(Complete Binary Tree)：

滿二叉樹(Perfect Binary Tree)：

完滿二叉樹(Full Binary Tree)：

參考資料：

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

簡單來說：堆排序是將數據看成是完全二叉樹、根據完全二叉樹的特性來進行排序的一種算法

最大堆要求節點的元素都要不小于其孩子，最小堆要求節點元素都不大于其左右孩子

那么處于最大堆的根節點的元素一定是這個堆中的最大值

這里我們討論最大堆：當前每個父節點都大于子節點

完全二叉樹有個特性：左邊子節點位置 = 當前父節點的兩倍 + 1，右邊子節點位置 = 當前父節點的兩倍 + 2

二、堆排序體驗

現在我們有一個完全二叉樹：左子樹和右子樹都符合最大堆-->父>子

但是我們會發現：根元素所在的數并不符合，明顯的是：1是小于7的

我們就對其進行交換，交換完之后我們會發現：右子樹又不符合了～

因為，右子樹變成了這樣：

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

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

可以發現的是：一次堆建立完之后，我們的最大值就在了堆的根節點上

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

接下來，剩下的數不斷進行建堆，交換就可以完成我們的堆排序了

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

三、堆排序代碼實現

比較當前父節點是否大于子節點，如果大于就交換，直到一趟建堆完成～

    /**
     * 建堆
     *
     * @param arrays          看作是完全二叉樹
     * @param currentRootNode 當前父節點位置
     * @param size            節點總數
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {

        if (currentRootNode < size) {
            //左子樹和右字數的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;

            //把當前父節點位置看成是最大的
            int max = currentRootNode;

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

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

值得注意的是：在上面體驗堆排序時，我們是左子樹和右子數都是已經有父>子這么一個條件的了。

顯然，一個普通的數組并不能有這種條件(父>子)，因此，我們往往是從數組最后一個元素來進行建堆

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

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

    }

完成第一次建堆之后，我們會發現最大值會在數組的首位：

接下來不斷建堆，然后讓數組最后一位與當前堆頂(數組第一位)進行交換即可排序：

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

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

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

    }

四、總結

堆排序是比其他排序要難一點，他用到了完全二叉樹這么一個特性來進行排序，代碼實現上也比其他排序要復雜一點。

參考資料：

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

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y

云服務器 GPU云服務器堆排序堆排序算法堆排序排序c語言 python的堆排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76363.html

方法和數組就是這么簡單！

摘要：數組就是一個簡單的線性序列，這使得元素訪問非常快速。堆區堆內存用來存放創建的對象和數組。堆內存中的實體不再被指向時，啟動垃圾回收機制，自動清除，這也是優于的表現之一中需要程序員手動清除。 showImg(https://segmentfault.com/img/remote/1460000019264541?w=600&h=242); 第三章方法和數組 3.1 概述還記得我們的He...

darkerXi 2019-08-16 17:40 評論0 收藏0
基于 Javascript 排序算法

摘要：適用于數據比較少或基本有序的情況。插入排序時間復雜度為，空間復雜度為，屬于穩定排序。算法適用于少量數據的排序。就像下圖這樣，可以理解桶的意思下圖是整個排序過程示意圖基數排序時間復雜度為，空間復雜度為，屬于穩定排序。寫在前面個人感覺：javascript對類似排序查找這樣的功能已經有了很好的封裝，以致于當我們想對數組排序的時候只需要調用arr.sort()方法，而查找數組元素也只需要...

tommego 2019-08-23 11:47 評論0 收藏0
希爾排序就這么簡單

摘要：這時就用簡單插入排序將數列直至已序從直觀上看希爾排序就是把數列進行分組不停使用插入排序，直至從宏觀上看起來有序，最后插入排序起來就容易了無須多次移位或交換。一、希爾排序介紹來源百度百科：希爾排序(Shells Sort)是插入排序的一種又稱縮小增量排序（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方...

paulli3 2019-08-19 10:43 評論0 收藏0
Java3y文章目錄導航

摘要：前言由于寫的文章已經是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導航。前言由于寫的文章已經是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導航。由于更新比較頻繁，因此隔一段時間才會更新目錄導航哦～想要獲取最新原創的技術文章歡迎關注我的公眾號：Java3y Java3y文章目錄導航 Java基礎泛型就這么簡單注解就這么簡單 Druid數據庫連接池...

KevinYan 2019-08-15 15:13 評論0 收藏0