堆排序

tangr206 發(fā)布于2019-08-16 12:30 / 1999人閱讀

摘要：計(jì)算機(jī)算法理論簡介建立初始堆首末元素互換即得到最大元素放入數(shù)組最末尾調(diào)整堆第二步的操作明顯會(huì)將堆破壞所以需要調(diào)整堆跳回第二步建立初始堆在建堆之前需要將數(shù)組轉(zhuǎn)成二叉樹圖方便理解如果將父左子右子當(dāng)做樹的最小單元組稱為父子單元那么只需要保證每個(gè)父

@(Study)[計(jì)算機(jī), 算法]

理論簡介

建立初始堆

首末元素互換, 即得到最大元素放入數(shù)組最末尾.

調(diào)整堆. 第二步的操作明顯會(huì)將堆破壞, 所以需要調(diào)整堆.

跳回第二步.

建立初始堆

在建堆之前需要將數(shù)組轉(zhuǎn)成二叉樹圖, 方便理解:

如果將父>左子|右子當(dāng)做樹的最小單元組, 稱為父子單元, 那么只需要保證每個(gè)父子單元滿足最大堆規(guī)則, 那么整體樹就滿足了最大堆.
==>定義一個(gè)方法(unitAdjust())用來調(diào)整父子單元, 將單元中最大的值推到該單元的根部, 成為父, 原來的父降到最大值之前的位置, 作為子. 但是這樣有可能使得以這個(gè)新子為父結(jié)點(diǎn)的下一層的父子單元不滿足最大堆規(guī)則. ==>設(shè)置規(guī)則, 如果發(fā)生了交換, 則遞歸調(diào)用方法自身, 調(diào)整新子為父結(jié)點(diǎn)的父子單元. 如此反復(fù).

上述過程可以說是自上而下的下鉆過程.

但是如果使得整個(gè)樹成為最大堆, 那么就是需要針對(duì)樹中的每個(gè)父子單元進(jìn)行調(diào)整. 只需要對(duì)樹中的每個(gè)非葉子節(jié)點(diǎn)進(jìn)行遍歷, 使用上述方法unitaAdjust()調(diào)整即可. 進(jìn)一分析, 可以發(fā)現(xiàn)這里有個(gè)問題: 遍歷的方向是自上而下還是自下而上呢?

如果自上而下會(huì)出現(xiàn)什么情況呢?
如下圖, 第一趟循環(huán)中, 操作的對(duì)象是以根結(jié)點(diǎn)34為父結(jié)點(diǎn)的父子單元. 循環(huán)體內(nèi)部將調(diào)用unitAdjust(), 34和50將互換, 由于發(fā)生了交換, unitAdust()方法將發(fā)生遞歸調(diào)用, 去操作以新子34為父結(jié)點(diǎn)的父子單元, 經(jīng)過比較, 未發(fā)生交換情況, 第一趟循環(huán)結(jié)束. 圖中發(fā)生了比較或者互換的位置以綠色標(biāo)出, 這時(shí)聰明的你不難發(fā)現(xiàn), 當(dāng)程序向下遍歷走到第三個(gè)節(jié)點(diǎn)時(shí), 便發(fā)生了重復(fù)比較, 當(dāng)然你或許能夠想到規(guī)避重復(fù)比較的方法, 但是我是沒有想出, 或者也可以認(rèn)為重復(fù)比較無所謂.

其實(shí), 換一種思路, 進(jìn)行自下而上遍歷情況就完全不一樣了.

從最后一個(gè)非葉子節(jié)點(diǎn)67開始, 67?90

50節(jié)點(diǎn)不動(dòng)

23?90, 觸發(fā)下鉆機(jī)制.

23?67

34?90, 觸發(fā)下鉆機(jī)制

34?67, 再次下鉆

未動(dòng)

最終得到初始堆如下圖所示, 其中藍(lán)色表示交換過位置.

可見, 整體是自下而上遍歷, 具體單元操作時(shí)采取自上而下, 總之, 自上而下和自下而上的相結(jié)合.

建立堆的過程其實(shí)有點(diǎn)冒泡的味道, 數(shù)值大逐漸的冒到上面, 好像密度大的即使開始在水底部, 但隨著遍歷, 密度大的終將上浮到上部.

堆排序

初始堆建立好了后, 堆頂?shù)脑刈匀痪褪亲畲笾? 于是將第一個(gè)元素和最后一個(gè)元素互換, 即完成將最大值放到最末尾, 完了第一次排序.

由于交換使得堆被破壞, 所以需要對(duì)的n-1個(gè)元素進(jìn)行調(diào)整, 使其成為堆. 具體做法就是調(diào)用unitAdjust()對(duì)以根節(jié)點(diǎn)為父結(jié)點(diǎn)的父子單元進(jìn)行調(diào)整, 剛換來的最末位元素自然會(huì)被移到子節(jié)點(diǎn)位置, 這樣遞歸調(diào)用機(jī)制被觸發(fā), 于是繼續(xù)保證所有下層調(diào)整為堆.

接著將倒數(shù)第二個(gè)元素和堆頂元素互換, ......如此反復(fù).

代碼實(shí)現(xiàn)

思路:

//建立初始堆//
for (i=n/2;i>=1;i--) {
    unitAdjust()
}
//堆排序//
for (i=n; i>=1; i--) {
    首末交換
    unitAdjust()調(diào)整
}

Java代碼:

測(cè)試結(jié)果:

10億長度, 內(nèi)存爆掉;
1億長度, 35693ms.

package LearningLog;

/*
 * - 10億長度, 內(nèi)存爆掉
 * - 1億長度, 35693ms.
 */

public class demo25 {
    public static void main(String[] args) {
        int[] arr=MyJava.randomArr(100000000, 10000,123);
//        System.out.println(Arrays.toString(arr));
//        initHeap(arr);
        long t0 = System.currentTimeMillis();
        heapSort(arr);
        long t1 = System.currentTimeMillis();
        System.out.println((t1-t0)+"ms");
//        System.out.println(Arrays.toString(arr));
    }
    /* ====unitAdjust()===========================================
     * 父子單元調(diào)整
     * I: 父結(jié)點(diǎn)的索引, 數(shù)組長度: 非常非常非常關(guān)鍵, 因?yàn)楹罄m(xù)調(diào)用的時(shí)候, 需要卡住最大的遍歷位置, 否則將會(huì)將尾部已經(jīng)排好序的較大數(shù)值頂?shù)缴厦嫒チ? 那就糟糕嘔吐了
     */
    public static void unitAdjust(int array[],int fatherNode, int sub_size) {
        int lchild = 2*fatherNode+1;
        int rchild = lchild+1;

        int max = fatherNode; // 默認(rèn)最大值索引就是父結(jié)點(diǎn)的索引
        int tmp = 0;
        if (fatherNode=0; i--) {
            unitAdjust(array, i, array.length);   //大的值不斷上浮
        }

    }
    
    /*
     * ====heapSort()=================================================
     * 堆排序
     */
    public static void heapSort(int[] array) {
        int tmp=0;
        //建立堆//
        initHeap(array);
        for(int i=array.length-1; i>=0; i--) {
            //首尾互換/
            tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            
            //剩下的i-1個(gè)元素需要調(diào)整//
            unitAdjust(array, 0, i); //始終只用調(diào)整第一個(gè)父子單元即可
        }
    }
    
    
    
    
    
}

云服務(wù)器 GPU云服務(wù)器堆排序堆排序算法堆排序排序c語言 python的堆排序

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71219.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

tangr206

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

震驚了！鴻蒙又多了一種開發(fā)方式Ets，讓更多的人趕上紅利！

閱讀 3169·2021-10-12 10:11
#大硬盤#AlphaVPS：2核/2G/1T HDD/3T流量/1Gbps/保加利亞/月付€5

閱讀 1877·2021-08-16 10:59
《CSS揭秘》-背景與邊框

閱讀 2886·2019-08-30 15:55
HTML拾遺

閱讀 1254·2019-08-30 14:19
使用Hexo+Github搭建屬于自己的博客

閱讀 2064·2019-08-29 17:03
mpvue的自定義組件中運(yùn)行$emit函數(shù)時(shí)輸入框光標(biāo)抖動(dòng)的解決辦法

閱讀 2499·2019-08-29 16:28
如何不花錢實(shí)現(xiàn)簡單的短信驗(yàn)證功能

閱讀 3246·2019-08-26 13:47
異步的JavaScript

閱讀 2918·2019-08-26 13:36

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

堆排序

相關(guān)文章

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

七大排序算法總結(jié)(java)

堆排序就這么簡單

基礎(chǔ)算法學(xué)習(xí)之(三):堆排序

常見八大排序（C語言實(shí)現(xiàn)）及動(dòng)圖演示

發(fā)表評(píng)論

0條評(píng)論

tangr206

男|高級(jí)講師

TA的文章

震驚了！鴻蒙又多了一種開發(fā)方式Ets，讓更多的人趕上紅利！

#大硬盤#AlphaVPS：2核/2G/1T HDD/3T流量/1Gbps/保加利亞/月付€5

《CSS揭秘》-背景與邊框

HTML拾遺

使用Hexo+Github搭建屬于自己的博客

mpvue的自定義組件中運(yùn)行$emit函數(shù)時(shí)輸入框光標(biāo)抖動(dòng)的解決辦法

如何不花錢實(shí)現(xiàn)簡單的短信驗(yàn)證功能

異步的JavaScript

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

堆排序

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！