<希爾排序>

詳細(xì)代碼請(qǐng)參考Algorithm源祈。參考代碼比文字好理解。
希爾排序雹姊，也稱遞減增量排序算法牲迫，是插入排序的一種高速而穩(wěn)定的改進(jìn)版本耐朴。因Donald Shell于1959年提出而得名。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)盹憎， 效率高筛峭， 即可以達(dá)到線性排序的效率；但插入排序一般來(lái)說(shuō)是低效的脚乡， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位蜒滩。該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序滨达，然后依次縮減增量再進(jìn)行排序奶稠，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)捡遍，再對(duì)全體元素進(jìn)行一次直接插入排序锌订。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的画株，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高辆飘。
希爾排序總結(jié)來(lái)說(shuō)就是把記錄按步長(zhǎng) gap 分組，對(duì)每組記錄采用直接插入排序方法進(jìn)行排序谓传。隨著步長(zhǎng)逐漸減小蜈项，所分成的組包含的記錄越來(lái)越多，當(dāng)步長(zhǎng)的值減小到 1 時(shí)续挟，整個(gè)數(shù)據(jù)合成為一組紧卒，構(gòu)成一組有序記錄，則完成排序诗祸。
算法分解

初始時(shí)跑芳，有一個(gè)大小為 10 的無(wú)序序列。在第一趟排序中直颅，我們不妨設(shè) gap1 = N / 2 = 5博个，即相隔距離為 5 的元素組成一組，可以分為 5 組功偿。接下來(lái)盆佣，按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序。
在第二趟排序中，我們把上次的 gap 縮小一半共耍，即 gap2 = gap1 / 2 = 2 (取整數(shù))投蝉。這樣每相隔距離為 2 的元素組成一組，可以分為 2 組征堪。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序瘩缆。
在第三趟排序中，再次把 gap 縮小一半佃蚜，即gap3 = gap2 / 2 = 1庸娱。 這樣相隔距離為 1 的元素組成一組，即只有一組谐算。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序熟尉。此時(shí)，排序已經(jīng)結(jié)束洲脂。
需要注意一下的是斤儿，圖中有兩個(gè)相等數(shù)值的元素 5 和 5 。我們可以清楚的看到恐锦，在排序過(guò)程中往果，兩個(gè)元素位置交換了。所以一铅，希爾排序是不穩(wěn)定的算法陕贮。
算法分析

步長(zhǎng)的選擇是希爾排序的重要部分。只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作潘飘。算法最開(kāi)始以一定的步長(zhǎng)進(jìn)行排序肮之。然后會(huì)繼續(xù)以一定步長(zhǎng)進(jìn)行排序，最終算法以步長(zhǎng)為1進(jìn)行排序卜录。當(dāng)步長(zhǎng)為1時(shí)戈擒，算法變?yōu)椴迦肱判颍@就保證了數(shù)據(jù)一定會(huì)被排序艰毒。
Donald Shell 最初建議步長(zhǎng)選擇為N/2并且對(duì)步長(zhǎng)取半直到步長(zhǎng)達(dá)到1筐高。雖然這樣取可以比O(N2)類的算法（插入排序）更好，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地现喳】粒可能希爾排序最重要的地方在于當(dāng)用較小步長(zhǎng)排序后，以前用的較大步長(zhǎng)仍然是有序的嗦篱。比如冰单，如果一個(gè)數(shù)列以步長(zhǎng)5進(jìn)行了排序然后再以步長(zhǎng)3進(jìn)行排序，那么該數(shù)列不僅是以步長(zhǎng)3有序灸促，而且是以步長(zhǎng)5有序诫欠。如果不是這樣涵卵，那么算法在迭代過(guò)程中會(huì)打亂以前的順序，那就不會(huì)以如此短的時(shí)間完成排序了荒叼。
直接插入排序和希爾排序的比較
直接插入排序是穩(wěn)定的轿偎；而希爾排序是不穩(wěn)定的。直接插入排序更適合于原始記錄基本有序的集合被廓。希爾排序的比較次數(shù)和移動(dòng)次數(shù)都要比直接插入排序少坏晦，當(dāng)N越大時(shí)，效果越明顯嫁乘。 在希爾排序中昆婿，增量序列g(shù)ap的取法必須滿足：最后一個(gè)步長(zhǎng)必須是 1 。 直接插入排序也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)蜓斧；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu)仓蛆。

<快排>

詳細(xì)代碼請(qǐng)參考Algorithm。參考代碼比文字好理解挎春。
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)看疙。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小直奋，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序能庆，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列帮碰。在平均狀況下相味，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較拾积。在最壞狀況下則需要Ο(n2)次比較殉挽，但這種狀況并不常見(jiàn)⊥厍桑快速排序使用分治法(Divide and conquer)策略來(lái)把一個(gè)串行(list)分為兩個(gè)子串行(sub-lists)斯碌。
算法步驟：
從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”(pivot)肛度，重新排序數(shù)列傻唾，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)承耿。在這個(gè)分區(qū)退出之后冠骄，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作加袋。遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序凛辣。遞歸的最底部情形，是數(shù)列的大小是零或一职烧，也就是永遠(yuǎn)都已經(jīng)被排序好了扁誓。雖然一直遞歸下去防泵，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡?iteration)中蝗敢，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去捷泞。
一趟快速排序的算法
1）設(shè)置兩個(gè)變量i、j寿谴，排序開(kāi)始的時(shí)候：i=0锁右，j=N-1；2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)讶泰，賦值給key骡湖，即key=A[0]；3）從j開(kāi)始向前搜索峻厚，即由后開(kāi)始向前搜索(j--)响蕴，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換惠桃；4）從i開(kāi)始向后搜索浦夷，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]辜王，將A[i]和A[j]互換劈狐；5）重復(fù)第3、4步呐馆，直到i=j肥缔； (3,4步中，沒(méi)找到符合條件的值汹来，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j续膳、i的值，使得j=j-1收班，i=i+1坟岔，直至找到為止。找到符合條件的值摔桦，進(jìn)行交換的時(shí)候i社付， j指針位置不變。另外邻耕，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候鸥咖，此時(shí)令循環(huán)結(jié)束）。

<鏈表>

鏈表是一種物理存儲(chǔ)單元上非連續(xù)兄世、非順序的存儲(chǔ)結(jié)構(gòu)啼辣，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成碘饼，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成熙兔。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域悲伶，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)住涉，操作復(fù)雜麸锉。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度舆声，比另一種線性表順序表快得多花沉，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)媳握。

詳細(xì)代碼請(qǐng)參考Algorithm碱屁。參考代碼比文字好理解。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)蛾找，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間娩脾，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)打毛，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域柿赊，空間開(kāi)銷比較大。鏈表最明顯的好處就是幻枉，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序碰声，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)熬甫，但是不允許隨機(jī)存取胰挑。鏈表有很多種不同的類型：?jiǎn)蜗蜴湵恚p向鏈表以及循環(huán)鏈表椿肩。
總結(jié)來(lái)說(shuō)瞻颂，相比較普通的線性結(jié)構(gòu)，鏈表結(jié)構(gòu)的優(yōu)勢(shì)是單個(gè)節(jié)點(diǎn)創(chuàng)建非常方便覆旱，普通的線性內(nèi)存通常在創(chuàng)建的時(shí)候就需要設(shè)定數(shù)據(jù)的大姓号蟆；節(jié)點(diǎn)的刪除非常方便扣唱，不需要像線性結(jié)構(gòu)那樣移動(dòng)剩下的數(shù)據(jù)；節(jié)點(diǎn)的訪問(wèn)方便团南，可以通過(guò)循環(huán)或者遞歸的方法訪問(wèn)到任意數(shù)據(jù)噪沙，但是平均的訪問(wèn)效率低于線性表。
線索二叉樹(shù)

線索二叉樹(shù)(保留遍歷時(shí)結(jié)點(diǎn)在任一序列的前驅(qū)和后繼的信息)：若結(jié)點(diǎn)有左子樹(shù)吐根，則其lchild域指示其左孩子正歼，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹(shù)拷橘，則其rchild域指示其右孩子局义，否則令rchild指示其后繼喜爷。還需在結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域LTag和RTag。LTag=0時(shí)萄唇，lchild域指示結(jié)點(diǎn)的左孩子檩帐，LTag=1時(shí)，lchild域指示結(jié)點(diǎn)的前驅(qū)另萤；RTag=0時(shí)湃密，rchild域指示結(jié)點(diǎn)的右孩子，RTag=1時(shí)四敞，rchild域指示結(jié)點(diǎn)的后繼泛源。
以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉線索鏈表，鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)忿危，叫做其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索达箍，加上線索的二叉樹(shù)稱為線索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化铺厨。若對(duì)二叉樹(shù)進(jìn)行中序遍歷幻梯，則所得的線索二叉樹(shù)稱為中序線索二叉樹(shù)，線索鏈表稱為為中序線索鏈表努释。線索二叉樹(shù)是一種物理結(jié)構(gòu)碘梢。
在中序線索樹(shù)找結(jié)點(diǎn)后繼的規(guī)律是：若其右標(biāo)志為1，則右鏈為線索伐蒂，指示其后繼煞躬，否則遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)（右子樹(shù)最左下的結(jié)點(diǎn)）為其后繼；找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若其左標(biāo)志為1逸邦，則左鏈為線索恩沛，指示其前驅(qū)，否則遍歷左子樹(shù)時(shí)最后訪問(wèn)的一個(gè)結(jié)點(diǎn)（左子樹(shù)中最右下的結(jié)點(diǎn)）為其前驅(qū)缕减。
在后序線索樹(shù)中找到結(jié)點(diǎn)的后繼分三種情況：若結(jié)點(diǎn)是二叉樹(shù)的根雷客，則其后繼為空；若結(jié)點(diǎn)是其雙親的右孩子桥狡，或是其雙親的左孩子且其雙親沒(méi)有右子樹(shù)搅裙，則其后繼即為雙親結(jié)點(diǎn)；若結(jié)點(diǎn)是其雙親的左孩子裹芝，且其雙親有右子樹(shù)部逮，則其后繼為雙親右子樹(shù)上按后序遍歷列出的第一個(gè)結(jié)點(diǎn)。

<冒泡排序>

冒泡排序是一種簡(jiǎn)單的排序算法嫂易。它重復(fù)地走訪過(guò)要排序的數(shù)列兄朋，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)怜械。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換颅和，也就是說(shuō)該數(shù)列已經(jīng)排序完成傅事。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法分析
比較相鄰的元素峡扩。如果第一個(gè)比第二個(gè)大蹭越，就交換他們兩個(gè)。對(duì)每一對(duì)相鄰元素作同樣的工作有额，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)般又。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)巍佑。針對(duì)所有的元素重復(fù)以上的步驟茴迁，除了最后一個(gè)。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟萤衰，直到?jīng)]有任何一對(duì)數(shù)字需要比較堕义。
原始待排序數(shù)組| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循環(huán))第一次兩兩比較6 > 2交換(內(nèi)循環(huán))交換前狀態(tài)| 6 | 2 | 4 | 1 | 5 | 9 |交換后狀態(tài)| 2 | 6 | 4 | 1 | 5 | 9 |
第二次兩兩比較,6 > 4交換交換前狀態(tài)| 2 | 6 | 4 | 1 | 5 | 9 |交換后狀態(tài)| 2 | 4 | 6 | 1 | 5 | 9 |
第三次兩兩比較,6 > 1交換交換前狀態(tài)| 2 | 4 | 6 | 1 | 5 | 9 |交換后狀態(tài)| 2 | 4 | 1 | 6 | 5 | 9 |
第四次兩兩比較,6 > 5交換交換前狀態(tài)| 2 | 4 | 1 | 6 | 5 | 9 |交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第五次兩兩比較,6 < 9不交換交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循環(huán))第一次兩兩比較2 < 4不交換交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |交換后狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |
第二次兩兩比較,4 > 1交換交換前狀態(tài)| 2 | 4 | 1 | 5 | 6 | 9 |交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第三次兩兩比較,4 < 5不交換交換前狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第四次兩兩比較,5 < 6不交換交換前狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循環(huán))第一次兩兩比較2 > 1交換交換后狀態(tài)| 2 | 1 | 4 | 5 | 6 | 9 |交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第二次兩兩比較,2 < 4不交換交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第三次兩兩比較,4 < 5不交換交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |交換后狀態(tài)| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循環(huán))無(wú)交換第五趟排序(外循環(huán))無(wú)交換
排序完畢,輸出最終結(jié)果1 2 4 5 6 9
詳細(xì)代碼請(qǐng)參考Algorithm。參考代碼比文字好理解脆栋。

<堆排序>

堆排序

詳細(xì)代碼請(qǐng)參考Algorithm倦卖。參考代碼比文字好理解。
堆排序是時(shí)間復(fù)雜度為O(N*logN)的排序方法椿争。是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法怕膛，它是選擇排序的一種∏刈伲可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素褐捻。堆分為大根堆和小根堆，是完全二叉樹(shù)椅邓。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值柠逞，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中景馁，需要使用的就是大根堆板壮，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂合住。
由于建初始堆所需的比較次數(shù)較多绰精，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序聊疲，輔助空間為O(1）.它是不穩(wěn)定的排序方法茬底。（排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個(gè)元素的話获洲，排序前 和排序后他們的相對(duì)位置不發(fā)生變化）
堆的存儲(chǔ)
一般都用數(shù)組來(lái)表示堆，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)互艾，然后再?gòu)母Y(jié)點(diǎn)開(kāi)始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最小的讯泣，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還小說(shuō)明不需要調(diào)整了纫普，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過(guò)程好渠。

堆排序
堆建好之后堆中第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ù)亦是堆绰播。堆實(shí)際上是二叉堆（Binary Heap），類似地可定義k叉堆尚困。
大根堆排序算法的基本操作：①建堆蠢箩，建堆是不斷調(diào)整堆的過(guò)程，從len/2處開(kāi)始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)谬泌，此處len是堆中元素的個(gè)數(shù)滔韵。建堆的過(guò)程是線性的過(guò)程，從len/2到0處一直調(diào)用調(diào)整堆的過(guò)程掌实，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度陪蜻，len/2表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過(guò)程贱鼻，結(jié)果是線性的O(n)宴卖。
②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過(guò)程中會(huì)用到，而且在堆排序過(guò)程中也會(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)整堆過(guò)程础米，這是一個(gè)遞歸的過(guò)程分苇。調(diào)整堆的過(guò)程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作屁桑，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的医寿。
③堆排序：堆排序是利用上面的兩個(gè)過(guò)程來(lái)進(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)整的過(guò)程，然后再將根節(jié)點(diǎn)取出竖瘾，這樣一直到所有節(jié)點(diǎn)都取出沟突。堆排序過(guò)程的時(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)庸论。