先說下本人目前的情況乱顾，盲目學習了半年的android知識，熟悉了四大組件和android項目中主流的一些框架和三方sdk,但是在實際求職中經常會被些基礎知識和基礎算法懟到一臉懵逼念链，所以說基本功可以看出一個人的實力当犯，或許這些知識在工作中用不到，但給面試官的感覺就是你啥也不懂菇存，今天就來總結一些算法知識却盘。
1 快速排序
快速排序由C. A. R. Hoare在1962年提出狰域，它的基本思想是：通過一趟排序要將排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小黄橘，然后再用此方法對這兩部分數(shù)據(jù)分別進行快速排序兆览，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序數(shù)列塞关。
算法步驟：1 從數(shù)列中挑出一個元素抬探，成為基準；
? ? ? ? ? ? ? ? ? ? 2 重新排序數(shù)列帆赢，所有比基準值小的元素都放在基準值的前面小压，所有比基準值大的元素都放在基準值后面线梗，相同的數(shù)放至任一邊，這個成為分區(qū)操作怠益；
? ? ? ? ? ? ? ? ? ? 3 遞歸地把小于基準值的子數(shù)列和大于基準值的子數(shù)列排序仪搔；
? ? ? ? ? ? ? ? ? ? 遞歸的最底部的情形，是數(shù)列的大小是零或者一溉痢，也就是已經排序好了僻造。
2 堆排序算法
堆實際上是一棵完全二叉樹，其任何一分頁節(jié)點的關鍵字不大于或者不小于其左右孩子節(jié)點的關鍵字孩饼。堆分為大頂堆和小頂堆髓削，大頂堆堆頂?shù)年P鍵字是所有關鍵字中最大的，小頂堆堆頂?shù)年P鍵字是所有關鍵字中最小的镀娶。
對于堆排序立膛，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程梯码，只不過構造初始堆是對所有的非葉節(jié)點都進行調整宝泵。
每次調整都是從父節(jié)點、左孩子節(jié)點轩娶、右孩子節(jié)點三者中選擇最大者跟父節(jié)點進行交換(交換之后可能造成被交換的孩子節(jié)點不滿足堆的性質儿奶，因此每次交換之后要重新對被交換的孩子節(jié)點進行調整)。有了初始堆之后就可以進行排序了鳄抒。
3 二分查找算法
二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法闯捎。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素许溅，則搜素過程結束瓤鼻；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找贤重，而且跟開始一樣從中間元素開始比較茬祷。如果在某一步驟數(shù)組為空，則代表找不到并蝗。這種搜索算法每一次比較都使搜索范圍縮小一半祭犯。折半搜索每次把搜索區(qū)域減少一半，時間復雜度為Ο(logn) 滚停。
4 深度優(yōu)先搜索 DFS
深度優(yōu)先搜索算法（Depth-First-Search）是搜索算法的一種沃粗。它沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支铐刘，當節(jié)點V的所有邊都已被探尋過，探索將回溯到發(fā)現(xiàn)節(jié)點V的那條邊的起始節(jié)點影晓。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止镰吵。如果還存在未被發(fā)現(xiàn)的節(jié)點檩禾，則選擇其中一個作為源節(jié)點并重復以上過程，整個進程反復進行到所有節(jié)點被訪問為止疤祭。DFS屬于盲目搜索盼产。
深度優(yōu)先搜索是圖論中的經典算法，利用深度優(yōu)先搜索算法可以產生目標圖的相應拓撲排序表勺馆，利用拓撲排序表可以方便的解決很多相關的圖論問題戏售，如最大路徑問題等等。一般用堆數(shù)據(jù)結構來輔助實現(xiàn)DFS算法草穆。
深度優(yōu)先遍歷圖算法步驟：
1.?訪問頂點v灌灾；
2.?依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷悲柱；直至圖中和v有路徑相通的頂點都被訪問锋喜；
3.?若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)豌鸡，重新進行深度優(yōu)先遍歷嘿般，直到圖中所有頂點均被訪問過為止。
