分類導(dǎo)航

堆排序詳解

發(fā)布時間：2017年05月08日作者： IT網(wǎng)絡(luò)文摘 (該文來自筆記，點擊查看原文)

堆排序是很有難度的算法。搞懂之后就覺得，"還行吧"。

先講個故事: 周日學(xué)校有開個實習(xí)的招聘會，沒有拿到大公司offer的我，當(dāng)然約上舍友走起啦。第一家，有人在面試了，那我就在旁邊聽下，只記得，"你會快排嗎? 堆排序呢? 現(xiàn)在你能寫出堆排序的算法??" 同為大三的面試者: "......"。

第二家，看了下，有招后臺，好極了。

招python開發(fā)的嗎? 用啥框架??　我用django的。很好，公司也有用django。我心里那個高興啊。后來，聊著聊著，不對勁。面試官話里透露著一股ds的氣息……我懷疑他還是學(xué)生……

他還說了公司的老板，竟然是我學(xué)校的老師，臥擦。我學(xué)校的老師竟然“兼職”去當(dāng)老板了，心理多少不爽啊!! 畢竟，平時上課，教得太水了，上課浪費我時間，還老是點名。(當(dāng)然少部分還是很好的)。后來換位思考，也就想通了。其實我也想當(dāng)老板……誰都這樣吧。

－－－－－－－－－－－－－－－－－－－－－－－－－華麗分割線－－－－－－－－－－－－－－－－－－－－－－－－－

堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節(jié)點的元素都要不小于其孩子，最小堆要求節(jié)點元素都不大于其左右孩子，兩者對左右孩子的大小關(guān)系不做任何要求，其實很好理解。有了上面的定義，我們可以得知，處于最大堆的根節(jié)點的元素一定是這個堆中的最大值。

其實我們的堆排序算法就是抓住了堆的這一特點，每次都取堆頂?shù)脑?，將其放在序列最后面，然后將剩余的元素重新調(diào)整為最大堆，依次類推，最終得到排序的序列。