好多大的公司都問算法玻侥，那么在這里總結(jié)一下。

其實(shí)我個人覺得在實(shí)際項(xiàng)目開發(fā)中并沒有用到很多的算法， 可能是我們的項(xiàng)目原因吧椿浓，就連平時見的最多的冒泡排序也沒有用上，但是面試的時候會問到闽晦，排序扳碍、查找、刪除仙蛉、插入等等笋敞，還有就是各大算法的思想和算法的實(shí)現(xiàn)，那好吧荠瘪，不積跬步夯巷，無以至千里，總是感覺算法很深奧巧还，那咱們一起掀開算法的神秘面紗吧鞭莽。

說到算法，不得不提到的就是時間復(fù)雜度和空間復(fù)雜度麸祷。這兩個度是什么呢澎怒，簡單的說就是這么多算法，總有個高低之分吧阶牍，看看誰更牛逼喷面！自古就有“文無第一，武無第二”一說走孽，所以各種算法到了一起總要“攀比”一下誰更牛逼惧辈，官方語言這樣描述的“算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率”。那么就有了衡量的標(biāo)準(zhǔn)磕瓷，就是這兩個度盒齿。

（1）時間復(fù)雜度：一般情況下念逞，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示边翁，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時翎承，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)符匾。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時間復(fù)雜度叨咖，簡稱時間復(fù)雜度。

分析：隨著模塊n的增大啊胶，算法執(zhí)行的時間的增長率和 f(n) 的增長率成正比甸各，所以 f(n) 越小，算法的時間復(fù)雜度越低焰坪，算法的效率越高趣倾。

2. 在計(jì)算時間復(fù)雜度的時候，先找出算法的基本操作某饰，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)誊酌，再找出 T(n) 的同數(shù)量級（它的同數(shù)量級有以下：1，log2n露乏，n，n log2n 涂邀，n的平方瘟仿，n的三次方，2的n次方比勉，n!）劳较，找出后，f(n) = 該數(shù)量級浩聋，若 T(n)/f(n) 求極限可得到一常數(shù)c观蜗，則時間復(fù)雜度T(n) = O(f(n))

根據(jù)“同中求異，異中求同”衣洁，我們設(shè)定x軸上邊去一個x＝10墓捻，可以得出如下結(jié)論：

（2）空間復(fù)雜度：類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(SpaceComplexity)S(n)定義為該算法所耗費(fèi)的存儲空間坊夫，它也是問題規(guī)模n的函數(shù)砖第。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度』吩洌空間復(fù)雜度(SpaceComplexity)是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度梧兼。一個算法在計(jì)算機(jī)存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間智听，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運(yùn)行過程中臨時占用的存儲空間這三個方面羽杰。

關(guān)于兩個復(fù)雜度渡紫，借用一個網(wǎng)友的說法就是“愚公的精神固然可敬，但是推土機(jī)和炸藥可能是更加實(shí)在和聰明”考赛。

好了惕澎，我們大概明白了什么是時間復(fù)雜度和空間復(fù)雜度了，（說實(shí)在的欲虚，光看概念我真的不怎么明白）那么我們經(jīng)常用的算法里面到底誰更厲害呢集灌？！下圖是咱們經(jīng)常用的排序的一個比較（誰能告訴我timsort是啥复哆？桶排序是啥欣喧？基數(shù)排序是啥？為啥沒有二分法梯找？還有二叉樹呢唆阿？）

上圖的紅黃綠棕色代表的意思就是，綠色效率更高锈锤，黃色一般驯鳖，紅色最差。

先來一發(fā)二分法的久免。

二分法查找

二分法查找的思想：首先保證這個數(shù)組是一個有序的數(shù)組浅辙。首先取到第一個數(shù)和最后一個數(shù)的下標(biāo)：min、max阎姥，然后取到中間數(shù)的下標(biāo)mid＝（min＋max）/2记舆，那么我們就能拿到中間數(shù)的數(shù)值，和我們要查找的數(shù)searchNum進(jìn)行比較呼巴，兩種結(jié)果：

（1）中間的數(shù)值大泽腮，那么searchNum就是中間數(shù)之前，那么我們將之前的max＝mid－1衣赶，（到這里就做到了二分：將數(shù)組的后半部分直接舍棄诊赊，不做比較，這也是數(shù)組必須是有序數(shù)組的原因府瞄。）再進(jìn)行上述操作進(jìn)行比較碧磅，直到作出判斷。

（2）中間的數(shù)值小摘能，那么searchNum就是中間數(shù)之后续崖，那么我們將之前的min＝mid＋1，（到這里就做到了二分：將數(shù)組的前半部分直接舍棄团搞，不做比較严望，這也是數(shù)組必須是有序數(shù)組的原因。）再進(jìn)行上述操作進(jìn)行比較逻恐，直到作出判斷像吻。

二分法排序

二分法排序思想：主要思想在于while：start和middle之間的“勾當(dāng)”將數(shù)組的前半部分排好序的直接忽略掉峻黍，不進(jìn)行比較。

我們給一個數(shù)組@[@12,@3,@23,@34,@35,@99,@98,@43];

（1）當(dāng)index＝0的時候拨匆，start＝0姆涩，end＝－1，middle＝0惭每，temp＝12骨饿，根據(jù)比較會進(jìn)入while，此時middle＝0台腥，if比較的時候不成立宏赘，跳出while。j＝－1＝end黎侈，那么for循環(huán)不進(jìn)入察署。repleace里面index＝0和temp交換，其實(shí)就是12自己和自己交換峻汉。

（2）當(dāng)index＝1的時候贴汪，start＝0，end＝0休吠，middle＝0扳埂，temp＝3，根據(jù)比較會進(jìn)入while瘤礁，此時middle＝0聂喇，if比較成立，進(jìn)入end＝－1蔚携。j＝0>end,則result[1]=result[0]，此時數(shù)組第二數(shù)變成了12克饶，再for循環(huán)酝蜒，j＝－1，不成立矾湃，跳出for循環(huán)亡脑。repleace里面index＝0和temp交換，那么數(shù)組第一個數(shù)變成了3邀跃，完成了交換霉咨。

......

（3）當(dāng)index＝7的時候，數(shù)組變成了@[@3,@12,@23,@34,@35,@98,@99,@43];start＝0拍屑，end＝6途戒，middle＝0，temp＝43僵驰，根據(jù)比較會進(jìn)入while喷斋，此時middle＝3唁毒，if比較得：34<43，進(jìn)入else星爪，start＝4浆西，再次進(jìn)入while，middle＝5顽腾，(二分法在此體現(xiàn)：start和middle之間將數(shù)組的前半部分排好序的直接忽略掉近零，不進(jìn)行比較)。if 比較得：98>43抄肖，則end＝4久信，再次比較start>end,所以跳出while進(jìn)入for循環(huán)。j＝6憎瘸，result[7]=result[6],此時數(shù)組最后一個數(shù)是99入篮。然后for循環(huán)進(jìn)行：j--得到j(luò)＝5，j>end幌甘，result[6]=result[5]潮售，此時數(shù)組倒數(shù)第二個數(shù)數(shù)是98，然后for循環(huán)進(jìn)行：j--得到j(luò)＝4锅风，j=end酥诽，此時跳出ror循環(huán)。repleace里面index＝5和temp交換皱埠，即43變成了在index為5的位置肮帐，也就是倒數(shù)第三個數(shù)。

此時數(shù)組排序完成边器。

注意：對于NSMutableArray的replaceObjectAtIndex:方法训枢，用B替換了A，擔(dān)心A的去向忘巧？不用擔(dān)心恒界，調(diào)用該方法的時候會對A自動調(diào)用release，所以我們不必?fù)?dān)心A的去向砚嘴。

再來一發(fā)冒泡：

冒泡排序

冒泡排序的思想就是（排序完成后是由大到小的順序）：1.比較相鄰的元素十酣。如果前面的比后邊的小，就交換他們兩個际长。對每一對相鄰元素作同樣的工作耸采，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)工育，最后的元素應(yīng)該會是最小的數(shù)虾宇。針對所有的元素重復(fù)以上的步驟，除了最后一個如绸。持續(xù)每次對越來越少的元素重復(fù)上面的步驟文留，直到?jīng)]有任何一對數(shù)字需要比較好唯。

簡單的說就是：比較相鄰元素，進(jìn)行交換燥翅。

簡單排序

簡單排序的核心思想：找準(zhǔn)時機(jī)骑篙、再做替換

和冒泡相比，冒泡每次都做替換森书，簡單排序是遍歷數(shù)組后找到最小元素的下標(biāo)后再做替換靶端。

簡單排序的時間復(fù)雜度也是O(N^2)。雖然簡單排序和冒泡排序的時間復(fù)雜度一樣凛膏，但是簡單排序在性能方面還是好很多的杨名，交換次數(shù)沒像冒泡那么頻繁。

希爾排序

希爾排序是一個基于插入排序的改進(jìn)型插入排序算法猖毫。由于插入排序一次只能交換相鄰的元素台谍，因此元素只能一點(diǎn)點(diǎn)的從數(shù)組的一端移動到另一端。如果最小的元素在數(shù)組的末尾的話吁断，那就需要N-1次移動趁蕊，因此對于插入排序的效率是非常低的。

注意：實(shí)際就是a[0]和a[h]比較仔役，a[1]和a[h+1]比較掷伙。。又兵。每比較完一輪后任柜，就縮小h的值。

理解：步長是決定希爾排序時間復(fù)雜度的關(guān)鍵沛厨，但是究竟應(yīng)該選擇什么樣的步長才是最好的宙地，目前還是一個數(shù)學(xué)難題。不過大量的研究數(shù)據(jù)表明逆皮，步長與時間復(fù)雜度存在以下關(guān)系：（看不懂下邊說的是啥意思俺裾ぁ）

Shell排序通過將數(shù)據(jù)分成不同的組，先對每一組進(jìn)行排序页屠，然后再對所有的元素進(jìn)行一次插入排序，以減少數(shù)據(jù)交換和移動的次數(shù)蓖柔。平均效率是O(nlogn)辰企。其中分組的合理性會對算法產(chǎn)生重要的影響。

按照不同步長對元素進(jìn)行插入排序况鸣，當(dāng)剛開始元素很無序的時候牢贸，步長最大，所以插入排序的元素個數(shù)很少镐捧，速度很快潜索；當(dāng)元素基本有序了臭增，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨咧裣啊Ｋ蕴芘祝柵判虻臅r間復(fù)雜度會比o(n^2)好一些。由于多次插入排序整陌，我們知道一次插入排序是穩(wěn)定的拗窃，不會改變相同元素的相對順序，但在不同的插入排序過程中泌辫，相同的元素可能在各自的插入排序中移動随夸，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的震放。

Shell排序比冒泡排序快5倍宾毒，比插入排序大致快2倍。Shell排序比起QuickSort殿遂，MergeSort诈铛，HeapSort慢很多。但是它相對比較簡單勉躺，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合癌瘾。它對于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。

最后饵溅，哪里不對的地方可以給我留言妨退，我會及時改進(jìn)的，謝謝大家蜕企。