來(lái)源：開發(fā)者應(yīng)該掌握的幾種排序算法 - 簡(jiǎn)書
來(lái)源：ios面試數(shù)據(jù)結(jié)構(gòu)與算法 - CSDN博客
首先要知道一個(gè)算法的好壞主要是從算法的時(shí)間復(fù)雜度赞别、空間復(fù)雜度和穩(wěn)定性來(lái)衡量汰瘫。
實(shí)際上把求解問(wèn)題的關(guān)鍵操作贸伐，如加減和比較運(yùn)算指定為基本操作蹦肴，然后把算法執(zhí)行基本操作的次數(shù)作為算法的時(shí)間復(fù)雜度浮定，而算法執(zhí)行期間占用的存儲(chǔ)單元的數(shù)量成為算法的空間復(fù)雜度扇苞。
一個(gè)算法的時(shí)間耗費(fèi)就是該算法鐘所有語(yǔ)句的頻率值和（記做T(n)）。當(dāng)問(wèn)題規(guī)模n無(wú)窮大時(shí)橡娄，T(n)的數(shù)量級(jí)成為時(shí)間復(fù)雜度诗箍，記做T(n)=O(f(n))
常見的 時(shí)間復(fù)雜度有O(1)叫常數(shù)階，O(n)叫做線性階挽唉，O(n^2)叫做平方階?
1滤祖、常數(shù)階
執(zhí)行的次數(shù)都是恒定的，不會(huì)隨著n的變化而變化瓶籽，所以單純的分支接受匠童，其時(shí)間復(fù)雜度也是O(1)。
2棘劣、線性階
線性階最具典型的例子就是迭代俏让。例如遍歷數(shù)組的中的每一個(gè)元素。整個(gè)遍歷過(guò)程總時(shí)間和數(shù)組的長(zhǎng)度呈正比（線性增長(zhǎng)）茬暇。
3首昔、對(duì)數(shù)階
var count =1?
while count < n {? ? ? ? ? ??
count = count *2
}
上述代碼中不難法相，當(dāng)count大于等于n的時(shí)候糙俗，整個(gè)循環(huán)就結(jié)束了勒奇。可以看出再次之前巧骚，循環(huán)執(zhí)行次數(shù)符合：2^x=n這個(gè)公式赊颠，x=log2n。所以上述代碼的時(shí)間復(fù)雜度為O(logn)劈彪。
4竣蹦、平方階
平方階就不做過(guò)多解釋，簡(jiǎn)單想象for循環(huán)嵌套for循環(huán)便理解了沧奴。
冒泡排序 - 簡(jiǎn)書
選擇排序 - 簡(jiǎn)書
插入排序 - 簡(jiǎn)書
快速排序 - 簡(jiǎn)書
歸并排序 - 簡(jiǎn)書
二分查找 - 簡(jiǎn)書
希爾排序 - 簡(jiǎn)書
五 堆排序?
堆?是具有下列性質(zhì)的完全二叉樹：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值痘括，稱為大頂堆；或者每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值稱為小頂堆滔吠。
來(lái)源：圖解排序算法(三)之堆排序 - dreamcatcher-cx - 博客園
堆排序的基本思想是：將待排序序列構(gòu)造成一個(gè)大頂堆纲菌，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)疮绷。將其與末尾元素進(jìn)行交換翰舌，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆冬骚，這樣會(huì)得到n個(gè)元素的次小值椅贱。如此反復(fù)執(zhí)行懂算，便能得到一個(gè)有序序列了
圖解：圖解排序算法(三)之堆排序 - dreamcatcher-cx - 博客園
六 哈夫曼樹
又稱最優(yōu)二叉樹，是指一組帶有確定確定權(quán)值的葉子節(jié)點(diǎn)所構(gòu)造的確有帶全路徑長(zhǎng)度最短的二叉樹庇麦，聰樹中的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了兩結(jié)點(diǎn)之間的路徑犯犁，路徑中的分支個(gè)數(shù)成為路徑長(zhǎng)度，二叉樹的路徑長(zhǎng)度是指由根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)的路徑長(zhǎng)度之和女器。
七 Hash算法
哈希算法詳解（附帶 iOS 開發(fā)中實(shí)際應(yīng)用） - 簡(jiǎn)書
Hash表采用一個(gè)映射函數(shù) f :key —> address 將關(guān)鍵字映射到該記錄在表中的存儲(chǔ)位置，從而在想要查找該記錄時(shí)住诸，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲(chǔ)位置驾胆，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)贱呐，而通過(guò)Hash函數(shù)和關(guān)鍵字計(jì)算出來(lái)的存儲(chǔ)位置（注意這里的存儲(chǔ)位置只是表中的存儲(chǔ)位置丧诺，并不是實(shí)際的物理地址）稱作為Hash地址。比如上述例子中奄薇，假如聯(lián)系人信息采用Hash表存儲(chǔ)驳阎，則當(dāng)想要找到 “l(fā)isi” 的信息時(shí)，直接根據(jù) “l(fā)isi” 和 Hash 函數(shù)計(jì)算出 Hash 地址即可馁蒂。
?Hash 表的優(yōu)缺點(diǎn)及注意點(diǎn)
優(yōu)點(diǎn)
哈希表的效率非常高呵晚，查找、插入沫屡、刪除操作只需要接近常量的時(shí)間即0(1）的時(shí)間級(jí)饵隙。如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表，哈希表的速度明顯比樹快沮脖，樹的操作通常需要O(N)的時(shí)間級(jí)金矛。哈希表不僅速度快，編程實(shí)現(xiàn)也相對(duì)容易勺届。如果不需要遍歷數(shù)據(jù)驶俊，不二的選擇。
缺點(diǎn)
它是基于數(shù)組的免姿，數(shù)組創(chuàng)建后難于擴(kuò)展饼酿。有些情況下，哈希表被基本填滿時(shí)养泡，性能下降得非常嚴(yán)重嗜湃，所以開發(fā)者必須要清楚表中將要存儲(chǔ)的數(shù)據(jù)量±窖冢或者也可以定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中购披，不過(guò)這個(gè)過(guò)程耗時(shí)相對(duì)比較大。
注意點(diǎn)
在設(shè)計(jì)Hash算法的時(shí)候肩榕。一定要保證相同字符串產(chǎn)生的 Hash 值相同刚陡，同時(shí)要盡量的減小Hash沖突的發(fā)生惩妇，這樣才算是好的 hash 算法。
iOS系統(tǒng)API給我們提供一個(gè)自動(dòng)過(guò)濾重復(fù)元素的容器 NSMutableSet/NSSet筐乳，如：當(dāng)我們向該實(shí)例對(duì)象中添加字符串時(shí)歌殃，如果重復(fù)添加兩個(gè)相同的字符串，集合中只會(huì)保留一個(gè)
