首先感謝朋友們對第一篇文章的鼎力支持，感動(dòng)中.......

今天說的是選擇排序，包括“直接選擇排序”和“堆排序”。

話說上次“冒泡排序”被快排虐了，而且“快排”贏得了內(nèi)庫的重用，眾兄弟自然眼紅，非要找快排一比高下。

這不今天就來了兩兄弟找快排算賬。

1.直接選擇排序：

先上圖：

說實(shí)話，直接選擇排序最類似于人的本能思想，比如把大小不一的玩具讓三歲小毛孩對大小排個(gè)序，

那小孩首先會在這么多玩具中找到最小的放在第一位，然后找到次小的放在第二位，以此類推。。。。。。

，小孩子多聰明啊，這么小就知道了直接選擇排序。羨慕中........

對的，小孩子給我們上了一課，

第一步： 我們拿80作為參照物（base），在80后面找到一個(gè)最小數(shù)20,然后將80跟20交換。

第二步: 第一位數(shù)已經(jīng)是最小數(shù)字了，然后我們推進(jìn)一步在30后面找一位最小數(shù)，發(fā)現(xiàn)自己最小，不用交換。

第三步：........

最后我們排序完畢。大功告成。

既然是來挑戰(zhàn)的，那就5局3勝制。

堆排序：

要知道堆排序，首先要了解一下二叉樹的模型。

下圖就是一顆二叉樹，具體的情況我后續(xù)會分享的。

那么堆排序中有兩種情況（看上圖理解）：

大根堆： 就是說父節(jié)點(diǎn)要比左右孩子都要大。

小根堆： 就是說父節(jié)點(diǎn)要比左右孩子都要小。

那么要實(shí)現(xiàn)堆排序,必須要做兩件事情：

第一：構(gòu)建大根堆。

首先上圖：

首先這是一個(gè)無序的堆，那么我們怎樣才能構(gòu)建大根堆呢？

第一步： 首先我們發(fā)現(xiàn)，這個(gè)堆中有2個(gè)父節(jié)點(diǎn)(2,,3);

第二步： 比較2這個(gè)父節(jié)點(diǎn)的兩個(gè)孩子（4，5），發(fā)現(xiàn)5大。

第三步： 然后將較大的右孩子（5）跟父節(jié)點(diǎn)（2）進(jìn)行交換，至此3的左孩子堆構(gòu)建完畢，

如圖：

第四步： 比較第二個(gè)父節(jié)點(diǎn)（3）下面的左右孩子（5，1），發(fā)現(xiàn)左孩子5大。

第五步： 然后父節(jié)點(diǎn)（3）與左孩子（5）進(jìn)行交換，注意，交換后，堆可能會遭到破壞，

必須按照以上的步驟一，步驟二，步驟三進(jìn)行重新構(gòu)造堆。

最后構(gòu)造的堆如下:

第二：輸出大根堆。

至此，我們把大根堆構(gòu)造出來了，那怎么輸出呢？我們做大根堆的目的就是要找出最大值，

那么我們將堆頂（5）與堆尾（2）進(jìn)行交換，然后將（5）剔除根堆，由于堆頂現(xiàn)在是（2），

所以破壞了根堆，必須重新構(gòu)造，構(gòu)造完之后又會出現(xiàn)最大值，再次交換和剔除，最后也就是俺們

要的效果了，

發(fā)現(xiàn)自己兄弟被別人狂毆， ，堆排序再也坐不住了，決定要和快排干一場。

同樣，快排也不甘示弱，誰怕誰？

堆排序此時(shí)心里很尷尬，雙雙被KO，心里想，一定要撈回面子，一定要贏，

于是堆排序提出了求“前K大問題”。（就是在海量數(shù)據(jù)中找出前幾大的數(shù)據(jù)），

快排一口答應(yīng)，小意思，沒問題。

雙方商定，在2w隨機(jī)數(shù)中找出前10大的數(shù)：

求前K大的輸出結(jié)果：

最后堆排序趕緊拉著直接選擇排序一路小跑了，因?yàn)榍笄癒大問題已經(jīng)不是他原本來的目的。

ps： 直接選擇排序的時(shí)間復(fù)雜度為：O(n^2)

堆排序的時(shí)間復(fù)雜度：O(NlogN)