堆排序是很有難度的算法。搞懂之后就覺得，"還行吧"。
先講個(gè)故事: 周日學(xué)校有開個(gè)實(shí)習(xí)的招聘會(huì)，沒有拿到大公司offer的我，當(dāng)然約上舍友走起啦。第一家，有人在面試了，那我就在旁邊聽下，只記得，"你會(huì)快排嗎? 堆排序呢? 現(xiàn)在你能寫出堆排序的算法??" 同為大三的面試者: "......"。
第二家，看了下，有招后臺(tái)，好極了。
招python開發(fā)的嗎? 用啥框架?? 我用django的。很好，公司也有用django。我心里那個(gè)高興啊。后來，聊著聊著，不對(duì)勁。面試官話里透露著一股ds的氣息……我懷疑他還是學(xué)生……
他還說了公司的老板，竟然是我學(xué)校的老師，臥擦。我學(xué)校的老師竟然“兼職”去當(dāng)老板了，心理多少不爽啊!! 畢竟，平時(shí)上課，教得太水了，上課浪費(fèi)我時(shí)間，還老是點(diǎn)名。(當(dāng)然少部分還是很好的)。后來換位思考，也就想通了。其實(shí)我也想當(dāng)老板……誰都這樣吧。
－－－－－－－－－－－－－－－－－－－－－－－－－華麗分割線－－－－－－－－－－－－－－－－－－－－－－－－－
堆分為最大堆和最小堆，其實(shí)就是完全二叉樹。最大堆要求節(jié)點(diǎn)的元素都要不小于其孩子，最小堆要求節(jié)點(diǎn)元素都不大于其左右孩子，兩者對(duì)左右孩子的大小關(guān)系不做任何要求，其實(shí)很好理解。有了上面的定義，我們可以得知，處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值。
其實(shí)我們的堆排序算法就是抓住了堆的這一特點(diǎn)，每次都取堆頂?shù)脑?，將其放在序列最后面，然后將剩余的元素重新調(diào)整為最大堆，依次類推，最終得到排序的序列。
其基本思想為(大頂堆)
將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)
將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn)
網(wǎng)友評(píng)論
