樹(shù)（續(xù)）

二叉樹(shù)

二叉排序樹(shù)

二叉排序樹(shù)恰梢，又叫二叉查找樹(shù)，它或者是一棵空樹(shù)晃酒；或者是具有以下性質(zhì)的二叉樹(shù)：

1. 若它的左子樹(shù)不空澳叉，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值隙咸；
2. 若它的右子樹(shù)不空沐悦，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3. 它的左右子樹(shù)也分別為二叉排序樹(shù)

• 二叉排序樹(shù)的建立
  集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我們的二叉排序樹(shù)中去存儲(chǔ)扎瓶，如果對(duì)我們創(chuàng)建好的二叉排序樹(shù)進(jìn)行中序搜索的話所踊，輸出的結(jié)果就是上面集合的有序序列。下方就是我們二叉排序樹(shù)從無(wú)到有的完整創(chuàng)建過(guò)程概荷。

1. 在初始化狀態(tài)下我們二叉排序樹(shù)的根節(jié)點(diǎn)為空，我們依次將集合中的元素通過(guò)搜索插入到二叉排序樹(shù)中合適的位置碌燕。
2. 首先在二叉排序中進(jìn)行搜索62的位置误证，樹(shù)為空，所以將62存入到二叉排序樹(shù)的根節(jié)點(diǎn)中修壕，及root=(62)愈捅。
3. 從集合中取出88，然后查找我們的二叉排序樹(shù)慈鸠，發(fā)現(xiàn)88大于我們的根節(jié)點(diǎn)62蓝谨，所以將88插入到62節(jié)點(diǎn)的右子樹(shù)中，即(62)->rightChild=(88)青团。
4. 從集合中取出58譬巫，然后從根節(jié)點(diǎn)開(kāi)始查找我們現(xiàn)有的二叉排序樹(shù)，發(fā)現(xiàn)55<62督笆，將55作為62的左結(jié)點(diǎn)芦昔，即(62)->leftChild=(55)。
5. 從集合中取出47娃肿，然后對(duì)二叉排序樹(shù)進(jìn)行搜索咕缎，發(fā)現(xiàn)47<55, 所以(55)->leftChild=(47)。
6. 從集合中取出35料扰，再次對(duì)二叉排序樹(shù)進(jìn)行搜索凭豪，發(fā)現(xiàn)35又小于47，所以(47)->leftChild=(35)晒杈。
7. 從集合中取出73嫂伞，再次對(duì)二叉排序樹(shù)進(jìn)行搜索，發(fā)現(xiàn)62<73<88, 所以有(88)->leftChild=(73)桐智。
   以此類(lèi)推末早，要做的事情就是不斷從集合中取值，然后對(duì)二叉排序樹(shù)進(jìn)行查找说庭，找到合適的插入點(diǎn)然磷，然后將相應(yīng)的節(jié)點(diǎn)進(jìn)行插入，具體步驟就不做過(guò)多贅述了刊驴。

• 二叉排序樹(shù)節(jié)點(diǎn)的刪除
  冒泡手法

二叉平衡樹(shù)

• 二叉排序樹(shù)的結(jié)點(diǎn)刪除：
  x為葉子結(jié)點(diǎn)姿搜，則直接刪除
  x只有左子樹(shù)xL或只有右子樹(shù)xR ,則令xL或xR直接成為雙親結(jié)點(diǎn)f的子樹(shù)寡润；
  x即有左子樹(shù)xL也有右子樹(shù)xR，在xL中選值最大的代替x舅柜，該數(shù)據(jù)按二叉排序樹(shù)的性質(zhì)應(yīng)在最右邊梭纹。
  平衡二叉樹(shù)：每個(gè)結(jié)點(diǎn)的平衡因子都為 1、－1致份、0 的二叉排序樹(shù)变抽。或者說(shuō)每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度最多差1的二叉排序樹(shù)氮块。

• 平衡二叉樹(shù)的平衡：
  左調(diào)整(新結(jié)點(diǎn)插入在左子樹(shù)上的調(diào)整)：
  LL(插入在結(jié)點(diǎn)左子樹(shù)的左子樹(shù)上)：旋轉(zhuǎn)前后高度都為h+1
  LR(新插入結(jié)點(diǎn)在左子樹(shù)的右子樹(shù)上)：旋轉(zhuǎn)前后高度仍為h+1
  右調(diào)整(新結(jié)點(diǎn)插入在右子樹(shù)上進(jìn)行的調(diào)整):
  RR(插入在的右子樹(shù)的右子樹(shù)上)：處理方法和 LL對(duì)稱(chēng)
  RL(插入在的右子樹(shù)的左子樹(shù)上)：處理方法和 LR對(duì)稱(chēng)

• 平衡樹(shù)建立方法：
  按二叉排序樹(shù)插入結(jié)點(diǎn)
  如引起結(jié)點(diǎn)平衡因子變?yōu)閨2|绍载，則確定旋轉(zhuǎn)點(diǎn)，該點(diǎn)是離根最遠(yuǎn)（或最接近于葉子的點(diǎn)）
  確定平衡類(lèi)型后進(jìn)行平衡處理滔蝉，平衡后以平衡點(diǎn)為根的子樹(shù)高不變
  最小二叉平衡樹(shù)的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個(gè)類(lèi)似于一個(gè)遞歸的數(shù)列击儡，可以參考Fibonacci數(shù)列，1是根節(jié)點(diǎn)蝠引，F(xiàn)(n-1)是左子樹(shù)的節(jié)點(diǎn)數(shù)量阳谍，F(xiàn)(n-2)是右子樹(shù)的節(jié)點(diǎn)數(shù)量。

• eg:
  鏡像二叉樹(shù)
  有限單詞拼寫(xiě)錯(cuò)誤檢查
  二叉樹(shù)中和為某一值的路徑
  二叉搜索樹(shù)第k個(gè)結(jié)點(diǎn)
  按之字順序打印二叉樹(shù)

圖(續(xù))

圖的存儲(chǔ)形式

1. 鄰接矩陣和加權(quán)鄰接矩陣
   無(wú)權(quán)有向圖：出度: i行之和螃概；入度: j列之和矫夯。
   無(wú)權(quán)無(wú)向圖：i結(jié)點(diǎn)的度: i行或i列之和。
   加權(quán)鄰接矩陣：相連為w谅年，不相連為∞
2. 鄰接表
   用頂點(diǎn)數(shù)組表茧痒、邊（弧）表表示該有向圖或無(wú)向圖
   頂點(diǎn)數(shù)組表：用數(shù)組存放所有的頂點(diǎn)融蹂。數(shù)組大小為圖頂點(diǎn)數(shù)n
   邊表（邊結(jié)點(diǎn)表）：每條邊用一個(gè)結(jié)點(diǎn)進(jìn)行表示旺订。同一個(gè)結(jié)點(diǎn)的所有的邊形成它的邊結(jié)點(diǎn)單鏈表。
   n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表最多有n(n-1)個(gè)邊表結(jié)點(diǎn)超燃。有n個(gè)頂點(diǎn)的無(wú)向圖最多有n(n-1)/2條邊区拳，此時(shí)為完全無(wú)向圖，而在鄰接表中每條邊存儲(chǔ)兩次意乓，所以有n(n-1)個(gè)結(jié)點(diǎn)

圖的遍歷

深度優(yōu)先搜索利用棧樱调，廣度優(yōu)先搜索利用隊(duì)列

環(huán)

環(huán)的檢測(cè)：黑白灰算法，死鎖檢測(cè)（拓?fù)渑判颍?/p>

• 在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之
• 從圖中刪除該頂點(diǎn)和所有以它為尾的弧
• 重復(fù)上述兩步届良，直至全部頂點(diǎn)均已輸出笆凌；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止(此時(shí)說(shuō)明圖中有環(huán)）

最短路徑

貪心算法：Dijkstra算法

最小生成樹(shù)

貪心算法：Prim算法、Kruskal算法

AOE網(wǎng)：

帶權(quán)的有向無(wú)環(huán)圖士葫，其中頂點(diǎn)表示事件乞而，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間慢显。在工程上常用來(lái)表示工程進(jìn)度計(jì)劃爪模。

1. 事件的最早發(fā)生時(shí)間（ve(j)）：從源點(diǎn)到j(luò)結(jié)點(diǎn)的最長(zhǎng)的路徑欠啤。意味著事件最早能夠發(fā)生的時(shí)間。
2. 事件的最遲發(fā)生時(shí)間（vl(j)）：不影響工程的如期完工屋灌，事件j必須發(fā)生的時(shí)間洁段。
3. 活動(dòng)ai由弧<j,k>表示，持續(xù)時(shí)間記為 dut<j,k>,則有:
   活動(dòng)的最早開(kāi)始時(shí)間：e(i)=ve(j)
   活動(dòng)的最遲開(kāi)始時(shí)間：l(i)=vl(k) - dut(<j , k >)
   活動(dòng)余量：l(i)-e(i)的差
4. 關(guān)鍵活動(dòng)：活動(dòng)余量為0的活動(dòng)
5. 關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)的一條路徑共郭，或者全部由關(guān)鍵活動(dòng)構(gòu)成的路徑祠丝。關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上。
6. 關(guān)鍵活動(dòng)組成了關(guān)鍵路徑落塑，關(guān)鍵路徑是圖中的最長(zhǎng)路徑纽疟，關(guān)鍵路徑長(zhǎng)度代表整個(gè)工期的最短完成時(shí)間，關(guān)鍵活動(dòng)延期完成憾赁，必將導(dǎo)致關(guān)鍵路徑長(zhǎng)度增加，即整個(gè)工期的最短完成時(shí)間增加散吵。關(guān)鍵路徑并不唯一龙考，當(dāng)有多條關(guān)鍵路徑存在時(shí)，其中一條關(guān)鍵路徑上的關(guān)鍵活動(dòng)時(shí)間縮短矾睦，只能導(dǎo)致本條關(guān)鍵路徑變成非關(guān)鍵路徑晦款，而無(wú)法縮短整個(gè)工期，因?yàn)槠渌P(guān)鍵路徑?jīng)]有變化枚冗。任何一條關(guān)鍵路徑上的關(guān)鍵活動(dòng)變長(zhǎng)了缓溅，都會(huì)使這條關(guān)鍵路徑變成更長(zhǎng)的關(guān)鍵路徑，并且導(dǎo)致其他關(guān)鍵路徑變成非關(guān)鍵路徑（如果關(guān)鍵路徑不唯一）赁温。關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間坛怪。所有的關(guān)鍵活動(dòng)提前完成,那么整個(gè)工程才會(huì)提前完成。關(guān)鍵路徑也不能任意縮短股囊，一旦縮短到一定程度袜匿，該關(guān)鍵活動(dòng)可能變成非關(guān)鍵活動(dòng)了。

查找

順序查找稚疹、折半查找居灯、索引查找、分塊查找 vs 二叉排序樹(shù)查找内狗，最優(yōu)二叉樹(shù)查找怪嫌，鍵樹(shù)查找，哈希表查找

• tips:
  時(shí)間：順序查找最差柳沙，二分最好岩灭，分塊介于兩者之間
  空間：分塊最大，需要增加索引數(shù)據(jù)的空間
  順序查找對(duì)表沒(méi)有特殊要求
  分塊時(shí)數(shù)據(jù)塊之間在物理上可不連續(xù)偎行。所以可以達(dá)到插入川背、刪除數(shù)據(jù)只涉及對(duì)應(yīng)的塊贰拿；另外，增加了索引的維護(hù)熄云。
  二分查找要求表有序膨更，所以若表的元素的插入與刪除很頻繁，維持表有序的工作量極大缴允。
  在表不大時(shí)荚守，一般直接使用順序查找。
  既希望較快的查找又便于線性表動(dòng)態(tài)變化的查找方法是哈希法查找练般。
  二叉排序樹(shù)查找矗漾，最優(yōu)二叉樹(shù)查找，鍵樹(shù)查找薄料，哈希法查找是動(dòng)態(tài)查找敞贡。分塊、順序摄职、折半誊役、索引順序查找均為靜態(tài)。分塊法應(yīng)該是將整個(gè)線性表分成若干塊進(jìn)行保存谷市，若動(dòng)態(tài)變化則可以添加在表的尾部（非順序結(jié)構(gòu)）蛔垢，時(shí)間復(fù)雜度是O(1)，查找復(fù)雜度為O(n)迫悠；若每個(gè)表內(nèi)部為順序結(jié)構(gòu)鹏漆，則可用二分法將查找時(shí)間復(fù)雜度降至O(logn)，但同時(shí)動(dòng)態(tài)變化復(fù)雜度則變成O(n)创泄；順序法是挨個(gè)查找艺玲，這種方法最容易實(shí)現(xiàn)，不過(guò)查找時(shí)間復(fù)雜度都是O(n)验烧，動(dòng)態(tài)變化時(shí)可將保存值放入線性表尾部板驳，則時(shí)間復(fù)雜度為O(1)；二分法是基于順序表的一種查找方式碍拆，時(shí)間復(fù)雜度為O(logn)若治；通過(guò)哈希函數(shù)將值轉(zhuǎn)化成存放該值的目標(biāo)地址，O（1）
  二叉樹(shù)的平均查找長(zhǎng)度為O(log2n)——O(n).二叉排序樹(shù)的查找效率與二叉樹(shù)的高度有關(guān)感混，高度越低端幼，查找效率越高。二叉樹(shù)的查找成功的平均查找長(zhǎng)度ASL不超過(guò)二叉樹(shù)的高度弧满。二叉樹(shù)的高度與二叉樹(shù)的形態(tài)有關(guān)婆跑，n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)高度最小，高度為[log2n]+1,n個(gè)節(jié)點(diǎn)的單只二叉樹(shù)的高度最大庭呜，高度為n滑进，此時(shí)查找成功的ASL為最大(n+1)/2犀忱，因此二叉樹(shù)的高度范圍為[log2n]+1——n.
  鏈?zhǔn)酱鎯?chǔ)不能隨機(jī)訪問(wèn)，必須是順序存儲(chǔ)

  
  
  一種二叉平衡樹(shù)

哈希表

在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣不經(jīng)過(guò)比較，一次存取就能得到元素冰悠。
哈希函數(shù)——在記錄的關(guān)鍵字與記錄的存儲(chǔ)位置之間建立的一種對(duì)應(yīng)關(guān)系。是從關(guān)鍵字空間到存儲(chǔ)位置空間的一種映象搀庶。
哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的位置信息铜异，并將記錄根據(jù)此信息放入表中哥倔，這樣構(gòu)成的表叫哈希表。
Hash查找適合于關(guān)鍵字可能出現(xiàn)的值的集合遠(yuǎn)遠(yuǎn)大于實(shí)際關(guān)鍵字集合的情形揍庄。
更適合查找咆蒿，不適合頻繁更新
Hash表等查找復(fù)雜依賴(lài)于Hash值算法的有效性，在最好的情況下蚂子，hash表查找復(fù)雜度為O(1)蜡秽。只有無(wú)沖突的hash_table復(fù)雜度才是O(1)。一般是O(c)缆镣，c為哈希關(guān)鍵字沖突時(shí)查找的平均長(zhǎng)度。插入试浙，刪除董瞻，查找都是O(1)。平均查找長(zhǎng)度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加,而是隨負(fù)載因子的增大而增大
由于沖突的產(chǎn)生田巴，使得哈希表的查找過(guò)程仍然是一個(gè)給定值與關(guān)鍵字比較的過(guò)程钠糊。
根據(jù)抽屜原理，沖突是不可能完全避免的壹哺，所以抄伍，選擇好的散列函數(shù)和沖突處理方法：
構(gòu)造一個(gè)性能好，沖突少的Hash函數(shù)
如何解決沖突
常用的哈希函數(shù)

直接定址法管宵。僅適合于：地址集合的大小 == 關(guān)鍵字集合的大小
數(shù)字分析法截珍。對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址箩朴。僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度岗喉。
平方取中法。以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址炸庞。
折疊法钱床。將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址埠居。移位疊加/間界疊加查牌。適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多事期，且每一位上數(shù)字分布大致均勻情況。
除留余數(shù)法纸颜。取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址兽泣，即H(key)=key%p，p<=m懂衩。
隨機(jī)數(shù)法撞叨。取關(guān)鍵字的偽隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)浊洞，適于關(guān)鍵字長(zhǎng)度不等的情況牵敷。
沖突解決

開(kāi)放定址法。當(dāng)沖突發(fā)生時(shí)法希，形成一個(gè)探查序列枷餐；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開(kāi)放的地址）苫亦，將發(fā)生沖突的記錄放到該地址中毛肋。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)屋剑，H(key)哈希函數(shù)润匙，m哈希表長(zhǎng)，di增量序列唉匾。缺點(diǎn)：刪除：只能作標(biāo)記孕讳，不能真正刪除；溢出巍膘；載因子過(guò)大厂财、解決沖突的算法選擇不好會(huì)發(fā)生聚集問(wèn)題。要求裝填因子α較小峡懈，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間璃饱。
線性探測(cè)再散列：di=1，2肪康，3荚恶，...，m-1
二次探測(cè)再散列：di=12,-12,22,-22,...梅鹦，±k2（k<=m/2）
偽隨機(jī)探測(cè)再散列: di為偽隨機(jī)數(shù)序列
鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中裆甩，并用一維數(shù)組存放頭指針。拉鏈法中可取α≥1齐唆，且結(jié)點(diǎn)較大時(shí)嗤栓，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間。一旦發(fā)生沖突茉帅，在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)就行叨叙。
其他方法：再哈希法、建立公共溢出區(qū)
在用拉鏈法構(gòu)造的散列表中堪澎，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)擂错。拉鏈法的缺點(diǎn)是：指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)樱蛤，開(kāi)放定址法較為節(jié)省空間钮呀。由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的,故它更適合于造表前無(wú)法確定表長(zhǎng)的情況。拉鏈法解決沖突時(shí)昨凡，需要使用指針爽醋，指示下一個(gè)元素的存儲(chǔ)位置
開(kāi)哈希表--鏈?zhǔn)降刂贩?閉哈希表--開(kāi)放地址法.開(kāi)哈希和閉哈希主要的區(qū)別在于，隨著哈希表的密集度提高便脊，使用閉哈希時(shí)蚂四，不僅會(huì)與相同哈希值的元素發(fā)生沖突，還容易與不同哈希值的元素發(fā)生沖突哪痰；而開(kāi)哈希則不受哈希表疏密與否的影響遂赠，始終只會(huì)與相同哈希值的元素沖突而已。所以在密集度變大的哈希表中查找時(shí)晌杰，顯然開(kāi)哈希的平均搜索長(zhǎng)度不會(huì)增長(zhǎng)跷睦。
設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到Hash表中需要做n(n-1)/2次線性探測(cè)肋演。如果使用二次探測(cè)再散列法將這n個(gè)關(guān)鍵字存入哈希表送讲，至少要進(jìn)行n(n+1)/2次探測(cè)
Hash查找效率：裝填因子=表中記錄數(shù)/表容量

排序

內(nèi)部排序：全部數(shù)據(jù)可同時(shí)放入內(nèi)存進(jìn)行的排序。
外部排序：文件中數(shù)據(jù)太多惋啃，無(wú)法全部調(diào)入內(nèi)存進(jìn)行的排序。

內(nèi)部排序

• 插入類(lèi)：

1. 直接插入排序监右。最壞情況是數(shù)據(jù)遞減序边灭，數(shù)據(jù)比較和移動(dòng)量最大，達(dá)到O(n2)健盒，最好是數(shù)據(jù)是遞增序绒瘦，比較和移動(dòng)最少為O(n)。趟數(shù)是固定的n-1扣癣，即使有序惰帽，也要依次從第二個(gè)元素開(kāi)始。排序趟數(shù)不等于時(shí)間復(fù)雜度父虑。
2. 折半插入排序 该酗。由于插入第i個(gè)元素到r[1]到r[i-1]之間時(shí)，前i個(gè)數(shù)據(jù)是有序的，所以可以用折半查找確定插入位置呜魄，然后插入悔叽。
3. 希爾排序【粜幔縮小增量排序娇澎。5-3-1。在實(shí)際應(yīng)用中睹晒，步長(zhǎng)的選取可簡(jiǎn)化為開(kāi)始為表長(zhǎng)n的一半（n/2）趟庄，以后每次減半，最后為1伪很。插入的改進(jìn)戚啥，最后一趟已基本有序，比較次數(shù)和移動(dòng)次數(shù)相比直接插入最后一趟更少

• 交換類(lèi)：

1. 冒泡排序是掰。O(n2)通常認(rèn)為冒泡是比較差的虑鼎，可以加些改進(jìn)，比如在一趟中無(wú)數(shù)據(jù)的交換键痛，則結(jié)束等措施炫彩。
   在數(shù)據(jù)已基本有序時(shí)，冒泡是一個(gè)較好的方法
   在數(shù)據(jù)量較少時(shí)（15個(gè)左右）可以用冒泡
2. 快速排序絮短。
   時(shí)間復(fù)雜度江兢。最好情況：每次支點(diǎn)總在中間，O(nlog2n)丁频，平均O(nlog2n)杉允。最壞，數(shù)據(jù)已是遞增或遞減席里，O(n2)叔磷。pivotkey的選擇越靠近中央，即左右兩個(gè)子序列長(zhǎng)度越接近奖磁，排序速度越快改基。越無(wú)序越快。
   空間復(fù)雜度咖为。需楋跽空間以實(shí)現(xiàn)遞歸，最壞情況：S(n)=O(n)躁染；一般情況：S(n)=O(log2n)
   在序列已是有序的情況下鸣哀，時(shí)間復(fù)雜度最高。原因：支點(diǎn)選擇不當(dāng)吞彤。改進(jìn)：隨機(jī)選取支點(diǎn)或最左我衬、最右、中間三個(gè)元素中的值處于中間的作為支點(diǎn)，通车挽可以避免最壞情況许昨。所以，快速排序在表已基本有序的情況下不合適褥赊。
   在序列長(zhǎng)度已較短時(shí)糕档，采用直接插入排序、起泡排序等排序方法拌喉。序列的個(gè)數(shù)通常取10左右速那。

• 選擇類(lèi)排序：

1. 簡(jiǎn)單選擇排序。O(n2)尿背《搜觯總比較次數(shù)n(n-1)/2。（類(lèi)似冒泡排序）
2. 堆排序田藐。建堆 O(n)荔烧，篩選排序O(nlogn)。找出若干個(gè)數(shù)中最大/最小的前K個(gè)數(shù)汽久，用堆排序是最好鹤竭。小根堆中最大的數(shù)一定是放在葉子節(jié)點(diǎn)上，堆本身是個(gè)完全二叉樹(shù)景醇，完全二叉樹(shù)的葉子節(jié)點(diǎn)的位置大于[n/2]臀稚。時(shí)間復(fù)雜度不會(huì)因?yàn)榇判蛐蛄械挠行虺潭榷淖儯谴判蛐蛄械挠行虺潭葧?huì)影響比較次數(shù)三痰。
3. 歸并排序吧寺。時(shí)間：與表長(zhǎng)成正比，若一個(gè)表表長(zhǎng)是m散劫，另一個(gè)是n稚机，則時(shí)間是O(m+n)。單獨(dú)一個(gè)數(shù)組歸并获搏，時(shí)間：O(nlogn)抒钱，空間：O(n)，比較次數(shù)介于(nlogn)/2和(nlogn)-n+1颜凯，賦值操作的次數(shù)是(2nlogn)。歸并排序算法比較占用內(nèi)存仗扬，但卻是效率高且穩(wěn)定的排序算法症概。在外排序中使用。歸并的趟數(shù)是logn早芭。
4. 基數(shù)排序彼城。在一般情況下，每個(gè)結(jié)點(diǎn)有 d 位關(guān)鍵字，必須執(zhí)行 t = d次分配和收集操作募壕。分配的代價(jià)：O(n)调炬；收集的代價(jià)：O(rd) （rd是基數(shù)）；總的代價(jià)為：O( d ×(n + rd))舱馅。適用于以數(shù)字和字符串為關(guān)鍵字的情況缰泡。
5. 枚舉排序，通常也被叫做秩排序代嗤，比較計(jì)數(shù)排序棘钞。對(duì)每一個(gè)要排序的元素，統(tǒng)計(jì)小于它的所有元素的個(gè)數(shù)干毅，從而得到該元素在整個(gè)序列中的位置宜猜，時(shí)間復(fù)雜度為O(n2)

• 排序算法的一些特點(diǎn)：

1. 堆排序、冒泡排序硝逢、快速排序在每趟排序過(guò)程中,都會(huì)有一個(gè)元素被放置在其最終的位置上姨拥。
2. 有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}，是快速排序算法一趟掃描的結(jié)果渠鸽。(拿Q作為分割點(diǎn),快速排序一輪叫乌。二路歸并，第一趟排序拱绑，得到 n / 2 個(gè)長(zhǎng)度為 2 的各自有序的子序列综芥，第二趟排序，得到 n / 4 個(gè)長(zhǎng)度為 4 的各自有序的子序列H Q C Y A P M S D R F X猎拨。如果是快速排序的話膀藐，第一個(gè)元素t將會(huì)被放到一個(gè)最準(zhǔn)確的位置，t前的數(shù)均小于t红省，后面的數(shù)均大于t额各。希爾排序每個(gè)小分組內(nèi)將會(huì)是有序的。堆排序吧恃，把它構(gòu)成一顆二叉樹(shù)的時(shí)候虾啦，該堆要么就是大根堆，要么就是小根堆痕寓，第一趟Y排在最后傲醉；冒泡，那么肯定會(huì)有數(shù)據(jù)下沉的動(dòng)作呻率，第一趟有A在第一位硬毕。)
3. 在文件"局部有序"或文件長(zhǎng)度較小的情況下,最佳內(nèi)部排序的方法是直接插入排序。（歸并排序要求待排序列已經(jīng)部分有序礼仗，而部分有序的含義是待排序列由若干有序的子序列組成吐咳，即每個(gè)子序列必須有序逻悠，并且其時(shí)間復(fù)雜度為O(nlog2n)；直接插入排序在待排序列基本有序時(shí)韭脊，每趟的比較次數(shù)大為降低童谒，即n-1趟比較的時(shí)間復(fù)雜度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每個(gè)元素距其最終位置不遠(yuǎn)也可用插入排序沪羔，效率最高的排序方法是插入排序）
4. 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是優(yōu)化冒泡和快速排序法饥伊。(插入排序和選擇排序不管序列的原始狀態(tài)是什么都要執(zhí)行n-1趟，優(yōu)化冒泡和快排不一定任内。仔細(xì)理解排序的次數(shù)和比較次數(shù)的區(qū)別)
5. 不穩(wěn)定的排序方法：快排撵渡，堆排，希爾死嗦，選擇
6. 要與關(guān)鍵字的初始排列次序無(wú)關(guān),那么就是最好趋距、最壞、一般的情況下排序時(shí)間復(fù)雜度不變, 總共有堆排序,歸并排序,選擇排序,基數(shù)排序.
   快速排序越除、Shell 排序节腐、歸并排序、直接插入排序的關(guān)鍵碼比較次數(shù)與記錄的初始排列有關(guān)摘盆。折半插入排序翼雀、選擇排序無(wú)關(guān)。(直接插入排序在完全有序的情況下每個(gè)元素只需要與他左邊的元素比較一次就可以確定他最終的位置孩擂；折半插入排序狼渊，比較次數(shù)是固定的，與初始排序無(wú)關(guān)类垦；快速排序狈邑，初始排序不影響每次劃分時(shí)的比較次數(shù)，都要比較n次蚤认，但是初始排序會(huì)影響劃分次數(shù)米苹，所以會(huì)影響總的比較次數(shù)，但快排平均比較次數(shù)最信樽痢蘸嘶；歸并排序在歸并的時(shí)候，如果右路最小值比左路最大值還大陪汽，那么只需要比較n次训唱，如果右路每個(gè)元素分別比左路對(duì)應(yīng)位置的元素大，那么需要比較2*n-1次挚冤，所以與初始排序有關(guān))
7. 精儉排序况增，即一對(duì)數(shù)字不進(jìn)行兩次和兩次以上的比較，插入和歸并是“精儉排序”你辣。插入排序巡通，前面是有序的，后面的每一個(gè)元素與前面有序的元素比較舍哄，比較過(guò)的就是有序的了宴凉，不會(huì)再比較一次。歸并每次合并后表悬，內(nèi)部都是有序的弥锄，內(nèi)部的元素之間不用再比較。選擇排序蟆沫，每次在后面的元素中找到最小的籽暇，找最小元素的過(guò)程是在沒(méi)有排好序的那部分進(jìn)行，所有肯定會(huì)比較多次饭庞。堆排序也需比較多次戒悠。

外部排序

生成合并段（run）：讀入文件的部分記錄到內(nèi)存－>在內(nèi)存中進(jìn)行內(nèi)部排序－>將排好序的這些記錄寫(xiě)入外存，形成合并段－>再讀入該文件的下面的記錄舟山，往復(fù)進(jìn)行绸狐，直至文件中的記錄全部形成合并段為止。

外部合并：將上一階段生成的合并段調(diào)入內(nèi)存累盗，進(jìn)行合并寒矿，直至最后形成一個(gè)有序的文件。

外部排序指的是大文件的排序若债，即待排序的記錄存儲(chǔ)在外存儲(chǔ)器上符相，待排序的文件無(wú)法一次裝入內(nèi)存，需要在內(nèi)存和外部存儲(chǔ)器之間進(jìn)行多次數(shù)據(jù)交換蠢琳，以達(dá)到排序整個(gè)文件的目的啊终。外部排序最常用的算法是多路歸并排序，即將原文件分解成多個(gè)能夠一次性裝入內(nèi)存的部分挪凑，分別把每一部分調(diào)入內(nèi)存完成排序孕索。然后，對(duì)已經(jīng)排序的子文件進(jìn)行多路歸并排序

不管初始序列是否有序, 冒泡躏碳、選擇排序時(shí)間復(fù)雜度是O(n^2),歸并搞旭、堆排序時(shí)間復(fù)雜度是O(nlogn）

外部排序的總時(shí)間 = 內(nèi)部排序（產(chǎn)出初始?xì)w并段）所需時(shí)間 + 外存信息讀取時(shí)間 + 內(nèi)部歸并所需的時(shí)間

外排中使用置換選擇排序的目的,是為了增加初始?xì)w并段的長(zhǎng)度。減少外存讀寫(xiě)次數(shù)需要減小歸并趟數(shù)

根據(jù)內(nèi)存容量設(shè)若干個(gè)輸入緩沖區(qū)和一個(gè)輸出緩沖區(qū)菇绵。若采用二路歸并肄渗，用兩個(gè)輸入緩沖。

歸并的方法類(lèi)似于歸并排序的歸并算法咬最。增加的是對(duì)緩沖的監(jiān)視翎嫡，對(duì)于輸入，一旦緩沖空永乌，要到相應(yīng)文件讀后續(xù)數(shù)據(jù)惑申，對(duì)于輸出緩沖具伍，一旦緩沖滿，要將緩沖內(nèi)容寫(xiě)到文件中去圈驼。

外排序和內(nèi)排序不只是考慮內(nèi)外排序算法的性能人芽，還要考慮IO數(shù)據(jù)交換效率的問(wèn)題，內(nèi)存存取速度遠(yuǎn)遠(yuǎn)高于外存绩脆。影響外排序的時(shí)間因素主要是內(nèi)存與外設(shè)交換信息的總次數(shù)

例子

1. 數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半萤厅，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}靴迫。由于數(shù)字2在數(shù)組中出現(xiàn)了5次惕味，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出2玉锌。如果不存在則輸出0
2. 逆序數(shù)
3. 加法的實(shí)現(xiàn)

4. 最大K個(gè)數(shù)

   
   
   some thoughts