先說下本人目前的情況，盲目學(xué)習(xí)了半年的android知識，熟悉了四大組件和android項目中主流的一些框架和三方sdk,但是在實際求職中經(jīng)常會被些基礎(chǔ)知識和基礎(chǔ)算法懟到一臉懵逼，所以說基本功可以看出一個人的實力，或許這些知識在工作中用不到，但給面試官的感覺就是你啥也不懂，今天就來總結(jié)一些算法知識。

1 快速排序

快速排序由C. A. R. Hoare在1962年提出，它的基本思想是：通過一趟排序要將排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再用此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序數(shù)列。

算法步驟：1 從數(shù)列中挑出一個元素，成為基準(zhǔn)；

? ? ? ? ? ? ? ? ? ? 2 重新排序數(shù)列，所有比基準(zhǔn)值小的元素都放在基準(zhǔn)值的前面，所有比基準(zhǔn)值大的元素都放在基準(zhǔn)值后面，相同的數(shù)放至任一邊，這個成為分區(qū)操作；

? ? ? ? ? ? ? ? ? ? 3 遞歸地把小于基準(zhǔn)值的子數(shù)列和大于基準(zhǔn)值的子數(shù)列排序；

? ? ? ? ? ? ? ? ? ? 遞歸的最底部的情形，是數(shù)列的大小是零或者一，也就是已經(jīng)排序好了。

2 堆排序算法

堆實際上是一棵完全二叉樹，其任何一分頁節(jié)點的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點的關(guān)鍵字。堆分為大頂堆和小頂堆，大頂堆堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最大的，小頂堆堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。

對于堆排序，最重要的兩個操作就是構(gòu)造初始堆和調(diào)整堆，其實構(gòu)造初始堆事實上也是調(diào)整堆的過程，只不過構(gòu)造初始堆是對所有的非葉節(jié)點都進行調(diào)整。

每次調(diào)整都是從父節(jié)點、左孩子節(jié)點、右孩子節(jié)點三者中選擇最大者跟父節(jié)點進行交換(交換之后可能造成被交換的孩子節(jié)點不滿足堆的性質(zhì)，因此每次交換之后要重新對被交換的孩子節(jié)點進行調(diào)整)。有了初始堆之后就可以進行排序了。

3 二分查找算法

二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時間復(fù)雜度為Ο(logn) 。

4 深度優(yōu)先搜索 DFS

深度優(yōu)先搜索算法（Depth-First-Search）是搜索算法的一種。它沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支，當(dāng)節(jié)點V的所有邊都已被探尋過，探索將回溯到發(fā)現(xiàn)節(jié)點V的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進程反復(fù)進行到所有節(jié)點被訪問為止。DFS屬于盲目搜索。

深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮恚猛負(fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題，如最大路徑問題等等。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)DFS算法。

深度優(yōu)先遍歷圖算法步驟：

1.?訪問頂點v；

2.?依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點都被訪問；

3.?若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。