程序員必須掌握的算法

　　一. 概述

　　在程序員這個(gè)群體的日常工作中，我們經(jīng)常會(huì)聽到一個(gè)詞----算法;也經(jīng)常接觸一個(gè)崗位----算法工程師。那么究竟什么是算法，作為一個(gè)程序員又需要掌握哪些算法那?

　　度娘對(duì)計(jì)算機(jī)算法的定義如下:

　　計(jì)算機(jī)算法是以一步接一步的方式，來詳細(xì)描述計(jì)算機(jī)該如何將輸入轉(zhuǎn)化為所要求的輸出的過程。或者說，算法是對(duì)計(jì)算機(jī)上執(zhí)行的計(jì)算過程的具體描述。

　　這個(gè)解釋有些小伙伴可能不是很能理解，那索爾就用一個(gè)容易理解例子給大家說一下：

　　比如有一個(gè)數(shù)組，存儲(chǔ)了10個(gè)隨機(jī)存入的整數(shù)，我們想對(duì)這個(gè)數(shù)組進(jìn)行排序。在這個(gè)排序的過程中，其實(shí)就用到了算法--排序算法。

　　再比如我們想要在一組數(shù)據(jù)中找到某個(gè)具體的數(shù)據(jù)，這個(gè)查找的過程也會(huì)用到算法--查找算法。

　　二. 常用算法

　　作為一個(gè)程序員，我們?cè)陂_發(fā)過程中還真的需要了解和使用一些算法來幫助我們完成編碼工作，下面索爾就來給大家介紹幾種常用的算法：

　　冒泡排序

　　選擇排序

　　插入排序

　　快速排序

　　二分查找

　　二叉樹算法

　　Dijkstra算法

　　字符串查找算法

　　1. 冒泡排序

　　1.1 算法簡(jiǎn)介

　　冒泡排序(Bubble Sort)是一種較為簡(jiǎn)單的排序算法。它會(huì)重復(fù)地走訪要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序(如從大到小、首字母從Z到A)錯(cuò)誤就把他們交換過來。走訪元素的工作會(huì)重復(fù)地進(jìn)行，直到?jīng)]有相鄰元素需要交換為止，也就是說直到該元素列完成排序。

　　這個(gè)算法之所以叫這個(gè)名字，是因?yàn)樵叫〉脑亟?jīng)過交換會(huì)慢慢“浮”到數(shù)列的最頂端(升序或降序排列)，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到最頂端一樣，故名“冒泡排序”。

　　1.2 冒泡原理

　　冒泡算法的基本原理就是比較相鄰的兩個(gè)元素，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。然后對(duì)每一對(duì)相鄰的兩個(gè)元素進(jìn)行同樣的工作，從第一對(duì)開始，直到最后的一對(duì)結(jié)尾，等到最后的元素應(yīng)該就是最大的元素。

　　我們只需要針對(duì)所有的元素，重復(fù)以上的步驟，除了最后一個(gè)。所以持續(xù)對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較為止。

　　我們可以參考下圖來理解冒泡算法：

　　2. 選擇排序

　　選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法，這是一種不穩(wěn)定的排序方法，其工作原理是：

　　第一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素，存放在序列的起始位置;

　　然后再從剩余的未排序元素中尋找到最小(大)的元素，然后再放到已排序的序列末尾;

　　以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。

　　3. 插入排序

　　3.1 算法簡(jiǎn)介

　　插入排序一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)。

　　3.2 插入原理

　　插入排序的工作方式像許多人排序一手撲克牌。開始時(shí)，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進(jìn)行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌。

　　插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的。按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列排為有序的過程，稱為插入排序。

　　4. 快速排序

　　快速排序(Quicksort)是對(duì)冒泡排序算法的一種改進(jìn)，其基本原理如下：

　　設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)(通常選用數(shù)組的第一個(gè)數(shù))作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。這樣一趟快速排序的算法是：

　　設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1;

　　以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0];

　　從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換;

　　從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]的值交換;

　　重復(fù)第3、4步，直到i==j;(3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束)。

　　5. 二分查找

　　5.1 算法簡(jiǎn)介

　　二分查找也稱折半查找(Binary Search)，這是一種效率較高的查找方法。但折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

　　5.2 算法原理

　　首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功;

　　否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表;

　　重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

　　6. 二叉樹算法

　　6.1 算法簡(jiǎn)介

　　二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^(i-1)個(gè)節(jié)點(diǎn)。深度為k的二叉樹至多有2^k- 1個(gè)結(jié)點(diǎn); 對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1。二叉樹算法常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

　　二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的有序樹，通常子樹被稱作“左子樹”(left subtree)和"右子樹"(right subtree)。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

　　6.2 算法特性

　　二叉樹算法通常具有如下特性：

　　(1). 在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1);

　　(2). 深度為h的二叉樹最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn);

　　(3). 對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;

　　(4). 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1

　　(5). 有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：若I為結(jié)點(diǎn)編號(hào)則 如果I>1，則其父結(jié)點(diǎn)的編號(hào)為I/2;如果2*IN，則無左兒子;如果2*I+1N，則無右兒子。

　　(6). 給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。

　　7. Dijkstra算法

　　迪杰斯特拉算法(Dijkstra)是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是從起始點(diǎn)開始，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。

　　Dijkstra算法一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。

　　Dijkstra算法可以解決如下問題：

　　在有向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短值。

　　8. 字符串搜索算法

　　字符串搜索算法是一種搜索算法，目的為在一長字符串中找出其是否包含某字符串。

　　字符串搜索算法工作的原理如下：

　　遍歷目標(biāo)字符串，使用指定的字符逐個(gè)比較，如果發(fā)現(xiàn)有相同的，返回這個(gè)元素的索引并結(jié)束遍歷;如果從頭比較到結(jié)束都沒有相同的，返回-1。

　　例如問題：在abcdefg中查找cd：

　　第一步：ab與cd比較;

　　第二步：bc與cd比較;

　　第三步：cd與cd比較

　　上面的操作會(huì)返回cd中c字符的索引。

　　字符串比較算法比較簡(jiǎn)單，效率也比較低，但是這種思想適合很多搜索場(chǎng)景。

　　三. 結(jié)語

　　上面索爾給大家介紹了一些基礎(chǔ)的常用算法，其實(shí)算法也是一門獨(dú)立的學(xué)科，通常和數(shù)據(jù)結(jié)構(gòu)一起學(xué)習(xí)，合適的算法在特定場(chǎng)景下能夠幫助我們更好更快的完成工作。

　　如果大家對(duì)Java算法感興趣可以聯(lián)系千鋒索爾老師，我們一起來體味算法中的奧妙。