web開(kāi)發(fā)中如何實(shí)現(xiàn)堆排序

這篇文章主要為大家展示了“web開(kāi)發(fā)中如何實(shí)現(xiàn)堆排序”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“web開(kāi)發(fā)中如何實(shí)現(xiàn)堆排序”這篇文章吧。

預(yù)備知識(shí)：堆結(jié)構(gòu)

堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱(chēng)為大頂堆；或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱(chēng)為小頂堆。

堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)（后面的【圖解數(shù)據(jù)結(jié)構(gòu)】?jī)?nèi)容會(huì)講解分析）所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。分為兩種方法：

• 大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；

• 小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。

算法步驟

1. 創(chuàng)建一個(gè)堆 H[0……n-1]；

2. 把堆首（最大值）和堆尾互換；

3. 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

4. 重復(fù)步驟 2，直到堆的尺寸為 1。

來(lái)源：https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序動(dòng)畫(huà)過(guò)程解釋

1. 首先，將所有的數(shù)字存儲(chǔ)在堆中

2. 按大頂堆構(gòu)建堆，其中大頂堆的一個(gè)特性是數(shù)據(jù)將被從大到小取出，將取出的數(shù)字按照相反的順序進(jìn)行排列，數(shù)字就完成了排序

3. 在這里數(shù)字 5 先入堆

4. 數(shù)字 2 入堆

5. 數(shù)字 7 入堆， 7 此時(shí)是最后一個(gè)節(jié)點(diǎn)，與最后一個(gè)非葉子節(jié)點(diǎn)（也就是數(shù)字 5 ）進(jìn)行比較，由于 7 大于 5 ，所以 7 和 5 交互

6. 按照上述的操作將所有數(shù)字入堆，然后從左到右，從上到下進(jìn)行調(diào)整，構(gòu)造出大頂堆

7. 入堆完成之后，將堆頂元素取出，將末尾元素置于堆頂，重新調(diào)整結(jié)構(gòu)，使其滿(mǎn)足堆定義

8. 堆頂元素?cái)?shù)字 7 取出，末尾元素?cái)?shù)字 4 置于堆頂，為了維護(hù)好大頂堆的定義，最后一個(gè)非葉子節(jié)點(diǎn)數(shù)字 5 與 4 比較，而后交換兩個(gè)數(shù)字的位置

9. 反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個(gè)序列有序

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

為了更好的讓讀者用自己熟悉的編程語(yǔ)言來(lái)理解動(dòng)畫(huà)，筆者將貼出多種編程語(yǔ)言的參考代碼，代碼全部來(lái)源于網(wǎng)上。

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

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

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

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

以上是“web開(kāi)發(fā)中如何實(shí)現(xiàn)堆排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！