一. 概述
在程序員這個(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)系千鋒索爾老師,我們一起來體味算法中的奧妙。