什么是算法編程？最常用的算法有哪些

編程算法是什么意思？相信問這個(gè)問題的同學(xué)一定是個(gè)零基礎(chǔ)剛剛?cè)腴T編程的小白，針對(duì)這個(gè)問題，本文將介紹編程算法的基本概念，并且盤點(diǎn)五個(gè)經(jīng)典的編程算法，幫助大家基礎(chǔ)入門。

1、算法是什么意思？

算法是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制，就是生活中的實(shí)際問題，轉(zhuǎn)化成數(shù)學(xué)問題去解決，將實(shí)際的抽象性問題轉(zhuǎn)換成數(shù)理性的問題去解決。

算法的五大特征是，有窮性，可行性，確切性，輸入，輸出。凡是任何一個(gè)算法都必須滿足這5個(gè)基本特征，只要是數(shù)學(xué)問題，不存在模棱兩可的事情。哪怕是概率問題在數(shù)學(xué)里專門有一門課程叫“概率論”與之對(duì)應(yīng)，能將這些不確定問題進(jìn)行數(shù)學(xué)化。

（1）有窮性

在有限的操作步驟內(nèi)完成。否則計(jì)算機(jī)會(huì)一直執(zhí)行到資源耗盡后死機(jī)。

（2）確定性

每個(gè)步驟確定，步驟的結(jié)果確定。算法執(zhí)行的過程是與計(jì)算機(jī)交互的過程，每一步必須明確且具有符合語(yǔ)言規(guī)則，否則計(jì)算機(jī)無(wú)法執(zhí)行，會(huì)報(bào)錯(cuò)。

（3）可行性

每個(gè)步驟有效執(zhí)行，得到確定的結(jié)果。每一個(gè)具體步驟在通過計(jì)算機(jī)實(shí)現(xiàn)時(shí)應(yīng)能夠使計(jì)算機(jī)完成，如果這一步驟在計(jì)算機(jī)上無(wú)法實(shí)現(xiàn)，也就達(dá)不到預(yù)期的目的，那么這一步驟是不完善的和不正確的，是不可行的。

（4）零個(gè)或多個(gè)輸入

從外界獲得信息。算法的過程可以無(wú)數(shù)據(jù)輸入，也可以有多種類型的多個(gè)數(shù)據(jù)輸入，需根據(jù)具體的問題加以分析。

（5）一個(gè)或多個(gè)輸出

算法得到的結(jié)果就是算法的輸出（不一定就是打印輸出）。算法的目的是為解決一個(gè)具體問題，一旦問題得以解決，就說(shuō)明采取的算法是正確的，而結(jié)果的輸出正是驗(yàn)證這一目的的最好方式。

2、經(jīng)典編程算法盤點(diǎn)

（1）快速排序算法

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο（n log n）次比較。在最壞狀況下則需要Ο（n2）次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他Ο（n log n） 算法更快。

因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)?？焖倥判蚴褂梅种畏ǎ―ivide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

算法步驟：

步驟1從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot），

步驟2重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

步驟3遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

（2）堆排序算法

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序的平均時(shí)間復(fù)雜度為Ο（nlogn） 。

算法步驟：

步驟1創(chuàng)建一個(gè)堆H［0..n-1］

步驟2把堆首（最大值）和堆尾互換

步驟3把堆的尺寸縮小1，并調(diào)用shift_down（0），目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置

步驟4重復(fù)步驟2，直到堆的尺寸為1

（3）歸并排序

歸并排序（Merge sort，臺(tái)灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

算法步驟：

步驟1申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列

步驟2設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

步驟3比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

步驟4重復(fù)步驟3直到某一指針達(dá)到序列尾

步驟5將另一序列剩下的所有元素直接復(fù)制到合并序列尾

（4）二分查找算法

二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜 素過程結(jié)束；

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

（5）BFPRT（線性查找算法）

BFPRT算法解決的問題十分經(jīng)典，即從某n個(gè)元素的序列中選出第k大（第k?。┑脑?，通過巧妙的分 析，BFPRT可以保證在最壞情況下仍為線性時(shí)間復(fù)雜度。該算法的思想與快速排序思想相似，當(dāng)然，為使得算法在最壞情況下，依然能達(dá)到o（n）的時(shí)間復(fù)雜 度，五位算法作者做了精妙的處理。

算法步驟：

步驟1將n個(gè)元素每5個(gè)一組，分成n/5（上界）組。

步驟2取出每一組的中位數(shù)，任意排序方法，比如插入排序。

步驟3遞歸的調(diào)用selection算法查找上一步中所有中位數(shù)的中位數(shù)，設(shè)為x，偶數(shù)個(gè)中位數(shù)的情況下設(shè)定為選取中間小的一個(gè)。

步驟4用x來(lái)分割數(shù)組，設(shè)小于等于x的個(gè)數(shù)為k，大于x的個(gè)數(shù)即為n-k。

步驟5若i==k，返回x；若i《k，在小于x的元素中遞歸查找第i小的元素；若i》k，在大于x的元素中遞歸查找第i-k小的元素。終止條件：n=1時(shí)，返回的即是i小元素。

以上就是編程算法的全部?jī)?nèi)容，相信看完大家都應(yīng)該明白了“編程算法是什么”。這些都是編程的基礎(chǔ)知識(shí)，大家一定要掌握哦！

編輯：jq