詳細(xì)代碼請(qǐng)參考Algorithm叨粘。參考代碼比文字好理解。
堆排序是時(shí)間復(fù)雜度為O(N*lgN)的排序方法瘤睹。是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法升敲，它是選擇排序的一種，可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素轰传，是完全二叉樹驴党。基本思想是把待排序的元素按照大小在二叉樹位置上排列获茬，排序好的元素要滿足：父節(jié)點(diǎn)的元素要大于等于其子節(jié)點(diǎn)港庄；這個(gè)過程叫做堆化過程，如果根節(jié)點(diǎn)存放的是最大的數(shù)恕曲，則叫做大根堆鹏氧；如果是最小的數(shù)，自然就叫做小根堆了佩谣。根據(jù)這個(gè)特性（大根堆根最大把还，小根堆根最小）茸俭，就可以把根節(jié)點(diǎn)拿出來吊履，然后再堆化下，再把根節(jié)點(diǎn)拿出來调鬓，循環(huán)到最后一個(gè)節(jié)點(diǎn)艇炎，就排序好了。
整個(gè)排序主要核心就是堆化過程腾窝，堆化過程一般是用父節(jié)點(diǎn)和他的孩子節(jié)點(diǎn)進(jìn)行比較冕臭，取最大的孩子節(jié)點(diǎn)和其進(jìn)行交換；但是要注意這應(yīng)該是個(gè)逆序的燕锥，先排序好子樹的順序辜贵，然后再一步步往上，到排序根節(jié)點(diǎn)上归形。然后又相反（因?yàn)楦?jié)點(diǎn)也可能是很小的）的托慨，從根節(jié)點(diǎn)往子樹上排序。最后才能把所有元素排序好暇榴。
由于建初始堆所需的比較次數(shù)較多厚棵，所以堆排序不適宜于記錄數(shù)較少的文件蕉世。堆排序是就地排序，輔助空間為O(1）.它是不穩(wěn)定的排序方法婆硬。（排序的穩(wěn)定性是指如果在排序的序列中狠轻，存在前后相同的兩個(gè)元素的話，排序前和排序后他們的相對(duì)位置不發(fā)生變化）
堆的存儲(chǔ)
一般都用數(shù)組來表示堆彬犯，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i – 1) / 2向楼。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2谐区。
堆的操作——插入刪除
每次插入都是將新數(shù)據(jù)放在數(shù)組最后湖蜕。可以發(fā)現(xiàn)從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必然為一個(gè)有序的數(shù)列宋列，現(xiàn)在的任務(wù)是將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)據(jù)中——這就類似于直接插入排序中將一個(gè)數(shù)據(jù)并入到有序區(qū)間中昭抒。
堆的刪除，按定義炼杖，堆中每次都只能刪除第0個(gè)數(shù)據(jù)灭返。為了便于重建堆，實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)坤邪，然后再從根結(jié)點(diǎn)開始進(jìn)行一次從上向下的調(diào)整婆殿。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最小的，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還小說明不需要調(diào)整了罩扇，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)婆芦。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過程。
堆排序
堆建好之后堆中第0個(gè)數(shù)據(jù)是堆中最小的數(shù)據(jù)喂饥。取出這個(gè)數(shù)據(jù)再執(zhí)行下堆的刪除操作消约。這樣堆中第0個(gè)數(shù)據(jù)又是堆中最小的數(shù)據(jù)，重復(fù)上述步驟直至堆中只有一個(gè)數(shù)據(jù)時(shí)就直接取出這個(gè)數(shù)據(jù)员帮。由于堆也是用數(shù)組模擬的或粮，故堆化數(shù)組后，第一次將A[0]與A[n - 1]交換捞高，再對(duì)A[0…n-2]重新恢復(fù)堆氯材。第二次將A[0]與A[n – 2]交換，再對(duì)A[0…n - 3]重新恢復(fù)堆硝岗，重復(fù)這樣的操作直到A[0]與A[1]交換氢哮。由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個(gè)數(shù)組就有序了型檀。
大根堆和小根堆
根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆冗尤，又稱最小堆。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆裂七，又稱最大堆皆看。堆中任一子樹亦是堆。堆實(shí)際上是二叉堆（Binary Heap）背零，類似地可定義k叉堆腰吟。
大根堆排序算法的基本操作：
①建堆，建堆是不斷調(diào)整堆的過程徙瓶，從len/2處開始調(diào)整毛雇，一直到第一個(gè)節(jié)點(diǎn)，此處len是堆中元素的個(gè)數(shù)倍啥。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程澎埠，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度虽缕，len/2表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過程蒲稳，結(jié)果是線性的O(n)氮趋。
②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會(huì)用到，而且在堆排序過程中也會(huì)用到江耀。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)剩胁，選出三者最大(或者最小)者，如果最大（邢楣）值不是節(jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)昵观，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程舌稀，這是一個(gè)遞歸的過程啊犬。調(diào)整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作壁查，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的觉至。
③堆排序：堆排序是利用上面的兩個(gè)過程來進(jìn)行的。首先是根據(jù)元素構(gòu)建堆睡腿。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)语御，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再將根節(jié)點(diǎn)取出席怪，這樣一直到所有節(jié)點(diǎn)都取出应闯。堆排序過程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)（調(diào)用一次）挂捻；調(diào)整堆的時(shí)間復(fù)雜度是lgn孽锥，調(diào)用了n-1次，所以堆排序的時(shí)間復(fù)雜度是O(nlgn)。
