堆排序是很有難度的算法。搞懂之后就覺(jué)得，"還行吧"。
先講個(gè)故事: 周日學(xué)校有開(kāi)個(gè)實(shí)習(xí)的招聘會(huì)，沒(méi)有拿到大公司offer的我，當(dāng)然約上舍友走起啦。第一家，有人在面試了，那我就在旁邊聽(tīng)下，只記得，"你會(huì)快排嗎? 堆排序呢? 現(xiàn)在你能寫(xiě)出堆排序的算法??" 同為大三的面試者: "......"。
第二家，看了下，有招后臺(tái)，好極了。
招python開(kāi)發(fā)的嗎? 用啥框架?? 我用django的。很好，公司也有用django。我心里那個(gè)高興啊。后來(lái)，聊著聊著，不對(duì)勁。面試官話里透露著一股ds的氣息……我懷疑他還是學(xué)生……
他還說(shuō)了公司的老板，竟然是我學(xué)校的老師，臥擦。我學(xué)校的老師竟然“兼職”去當(dāng)老板了，心理多少不爽啊!! 畢竟，平時(shí)上課，教得太水了，上課浪費(fèi)我時(shí)間，還老是點(diǎn)名。(當(dāng)然少部分還是很好的)。后來(lái)?yè)Q位思考，也就想通了。其實(shí)我也想當(dāng)老板……誰(shuí)都這樣吧。
－－－－－－－－－－－－－－－－－－－－－－－－－華麗分割線－－－－－－－－－－－－－－－－－－－－－－－－－
堆分為最大堆和最小堆，其實(shí)就是完全二叉樹(shù)。最大堆要求節(jié)點(diǎn)的元素都要不小于其孩子，最小堆要求節(jié)點(diǎn)元素都不大于其左右孩子，兩者對(duì)左右孩子的大小關(guān)系不做任何要求，其實(shí)很好理解。有了上面的定義，我們可以得知，處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值。
其實(shí)我們的堆排序算法就是抓住了堆的這一特點(diǎn)，每次都取堆頂?shù)脑兀瑢⑵浞旁谛蛄凶詈竺?，然后將剩余的元素重新調(diào)整為最大堆，依次類(lèi)推，最終得到排序的序列。
其基本思想為(大頂堆)
將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)
將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn)
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式