千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁  >  技術(shù)干貨  > 程序員必須掌握的算法

程序員必須掌握的算法

來源:千鋒教育
發(fā)布人:wjy
時(shí)間: 2023-03-02 16:48:00 1677746880

  一. 概述

  在程序員這個(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ù)字需要比較為止。

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

程序員必須掌握的算法1206

  2. 選擇排序

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

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

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

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

程序員必須掌握的算法1672

  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è)序列排為有序的過程,稱為插入排序。

程序員必須掌握的算法2429

  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é)束)。

程序員必須掌握的算法3272

  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í)查找不成功。

程序員必須掌握的算法3841

  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)。

程序員必須掌握的算法4758

  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)的最短值。

程序員必須掌握的算法5391

  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)景。

程序員必須掌握的算法5944

  三. 結(jié)語

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

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

tags:
聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
python字符串截???

在Python中,字符串是一種非常常見的數(shù)據(jù)類型,它可以用來表示文本、數(shù)字、符號(hào)等內(nèi)容。在實(shí)際應(yīng)用中,我們經(jīng)常需要對(duì)字符串進(jìn)行截取,以便獲取...詳情>>

2023-11-02 17:56:27
Python socket C/S結(jié)構(gòu)的聊天室應(yīng)用實(shí)現(xiàn)?

隨著互聯(lián)網(wǎng)的發(fā)展,聊天室應(yīng)用成為人們?nèi)粘I钪惺殖R姷囊环N社交方式。Python語言的Socket模塊是實(shí)現(xiàn)網(wǎng)絡(luò)通信的重要工具,可以輕松地實(shí)現(xiàn)C/...詳情>>

2023-11-02 17:53:38
用while求1到100的奇數(shù)和?

在計(jì)算機(jī)編程中,循環(huán)語句是非常重要的一部分。而while語句是其中最基本也是最常用的一種。它的作用是在滿足一定條件的情況下,重復(fù)執(zhí)行一段代...詳情>>

2023-11-02 17:50:57
python創(chuàng)建一個(gè)集合?

在Python中,集合是一種無序且不重復(fù)的數(shù)據(jù)類型,可以用于存儲(chǔ)一組元素。創(chuàng)建一個(gè)集合非常簡(jiǎn)單,只需要使用大括號(hào){}或者set()函數(shù)即可。使用大...詳情>>

2023-11-02 17:34:02
linux改文件屬主命令?

Linux文件相關(guān)命令1、命令一:cat cat命令應(yīng)該是在Linux中查看文件內(nèi)容最常見的命令了。使用cat命令會(huì)打印指定文件的所有內(nèi)容到標(biāo)準(zhǔn)輸出上,比...詳情>>

2023-10-31 19:58:15