堆排序是很有難度的算法。搞懂之后就覺得，"還行吧"。
先講個故事: 周日學(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)整為最大堆，依次類推，最終得到排序的序列。
其基本思想為(大頂堆)
將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)
將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn)
網(wǎng)友評論
