• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 70  文章 - 160  trackbacks - 0

            公告:
            知識共享許可協議
            本博客采用知識共享署名 2.5 中國大陸許可協議進行許可。本博客版權歸作者所有,歡迎轉載,但未經作者同意不得隨機刪除文章任何內容,且在文章頁面明顯位置給出原文連接,否則保留追究法律責任的權利。 具體操作方式可參考此處。如您有任何疑問或者授權方面的協商,請給我留言。

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            搜索

            •  

            積分與排名

            • 積分 - 179004
            • 排名 - 147

            最新評論

            閱讀排行榜

            評論排行榜

            建議先看看前言:http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

            首先介紹幾個概念:

            衛星數據:一個帶排序的的數通常是有一個稱為記錄的數據集組成的,每一個記錄有一個關鍵字key,記錄的其他數據稱為衛星數據。

            原地排序:在排序輸入數組時,只有常數個元素被存放到數組以外的空間中去。

             

            在第二章介紹了兩種排序:插入排序和合并排序,接下來兩章要介紹的是推排序和快速排序,這四個排序都屬于比較排序(comparison sort)。

             

            我以前總結過堆排序,并具體實現了堆排序,代碼中給出了詳細的注釋,所以在這里就不重復發了,大家可以去看看,個人覺得總結的還是比較給力的:

            http://www.wutianqi.com/?p=1820

            這里再補充幾點:

            1.區別length[A]和heap-sort[A]。(P73)(這個在下一篇的優先級隊列中將會具體區別)

            2.總體上看堆排序由三個函數組成:①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

             

            另外,在這里給大家補充一點個人經驗,有時理論難以理解,代碼難以理解,這個時候,就要靠秘訣了:拿起手中的筆和紙,自己給出一組輸入,按照書上的代碼,自己去模擬這組輸入的執行過程。(這個過程人人都知道,但并不是人人都去做了!學算法,就要自己去模擬,去畫圖,去推!怎么樣容易理解就怎么去做!)

            所以這也是我喜歡《算法導論》的原因,接下來,就要強烈推薦大家看《算法導論》上非常非常給力的堆排序實現圖了—圖6-4。

             

             

            總結:本章最基礎也是最重要的就是理解堆這種結構!

            堆是什么?來看看《算法導論》上的圖6-1:

            dui

            圖(a)是一個最大堆,圖(b)是最大堆的數組表示。可以看到堆的數組并不是已排序好的。

            讓我們來回憶下最大堆的定義(P74):

            在最大堆中,最大堆特性是指除了根以外的每個結點i,有A[PARENT(i)] >= A[i]。這樣,堆的最大元素就存放在根結點中。

            對,堆排序就是利用的這個特性—“堆的最大元素就存放在根結點中”

            每次堆化,這樣就找到了當前堆的最大元素。

            所以說,理解了其本質特征,堆排序其實很簡單的。

            至于堆排序的具體應用,在后面的最短路算法—Dijkstra中,會用到由堆來優化普通的Dijkstra算法。

            下一篇將實現最大優先級隊列。

            Tanky Woo 標簽:
            posted on 2011-04-15 12:43 Tanky Woo 閱讀(1314) 評論(0)  編輯 收藏 引用
            久久综合中文字幕| 久久99精品久久久久子伦| 久久久久久国产a免费观看不卡| 狠狠人妻久久久久久综合蜜桃| 色综合久久88色综合天天 | 久久伊人五月丁香狠狠色| 国产V综合V亚洲欧美久久| 人妻少妇精品久久| 国产一区二区三区久久精品| 亚洲精品午夜国产va久久| 伊人久久免费视频| 香蕉久久av一区二区三区| 99热成人精品免费久久| 精品久久久久久久久午夜福利| 人人狠狠综合88综合久久| 久久精品国产精品国产精品污 | 久久婷婷五月综合色高清| 久久亚洲高清综合| 91久久九九无码成人网站| 久久久久亚洲av无码专区导航| 人妻丰满?V无码久久不卡| 久久不见久久见免费影院www日本| 久久国产欧美日韩精品| 亚洲国产精品无码久久久蜜芽| 亚洲午夜无码AV毛片久久| 久久www免费人成精品香蕉| 青青草国产精品久久| 久久精品国产亚洲AV高清热| 久久毛片一区二区| 久久精品国产99国产精品导航| 国产精品免费久久久久久久久 | 国产成人精品久久| 久久精品国产99久久久古代| 欧美精品国产综合久久| 久久久久久午夜精品| 亚洲愉拍99热成人精品热久久 | 日本强好片久久久久久AAA| 亚洲AV无码成人网站久久精品大| 中文字幕人妻色偷偷久久| 久久久久亚洲AV无码专区首JN| 97精品国产97久久久久久免费|