編程算法是什么意思?相信問這個問題的同學一定是個零基礎剛剛入門編程的小白,針對這個問題,本文將介紹編程算法的基本概念,并且盤點五個經典的編程算法,幫助大家基礎入門。
1、算法是什么意思?
算法是一系列解決問題的清晰指令,算法代表著用系統的方法描述解決問題的策略機制,就是生活中的實際問題,轉化成數學問題去解決,將實際的抽象性問題轉換成數理性的問題去解決。
算法的五大特征是,有窮性,可行性,確切性,輸入,輸出。凡是任何一個算法都必須滿足這5個基本特征,只要是數學問題,不存在模棱兩可的事情。哪怕是概率問題在數學里專門有一門課程叫“概率論”與之對應,能將這些不確定問題進行數學化。
(1)有窮性
在有限的操作步驟內完成。否則計算機會一直執行到資源耗盡后死機。
(2)確定性
每個步驟確定,步驟的結果確定。算法執行的過程是與計算機交互的過程,每一步必須明確且具有符合語言規則,否則計算機無法執行,會報錯。
(3)可行性
每個步驟有效執行,得到確定的結果。每一個具體步驟在通過計算機實現時應能夠使計算機完成,如果這一步驟在計算機上無法實現,也就達不到預期的目的,那么這一步驟是不完善的和不正確的,是不可行的。
(4)零個或多個輸入
從外界獲得信息。算法的過程可以無數據輸入,也可以有多種類型的多個數據輸入,需根據具體的問題加以分析。
(5)一個或多個輸出
算法得到的結果就是算法的輸出(不一定就是打印輸出)。算法的目的是為解決一個具體問題,一旦問題得以解決,就說明采取的算法是正確的,而結果的輸出正是驗證這一目的的最好方式。
2、經典編程算法盤點
(1)快速排序算法
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下,排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他Ο(n log n) 算法更快。
因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。
算法步驟:
步驟1從數列中挑出一個元素,稱為 “基準”(pivot),
步驟2重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后,該基準就處于數列的中間位置。這個稱為分區(partition)操作。
步驟3遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。遞歸的最底部情形,是數列的大小是零或一,也就是永遠都已經被排序好了。雖然一直遞歸下去,但是這個算法總會退出,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最后的位置去。
(2)堆排序算法
堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,并同時滿足堆積的性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。堆排序的平均時間復雜度為Ο(nlogn) 。
算法步驟:
步驟1創建一個堆H[0..n-1]
步驟2把堆首(最大值)和堆尾互換
步驟3把堆的尺寸縮小1,并調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
步驟4重復步驟2,直到堆的尺寸為1
(3)歸并排序
歸并排序(Merge sort,臺灣譯作:合并排序)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。
算法步驟:
步驟1申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合并后的序列
步驟2設定兩個指針,最初位置分別為兩個已經排序序列的起始位置
步驟3比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置
步驟4重復步驟3直到某一指針達到序列尾
步驟5將另一序列剩下的所有元素直接復制到合并序列尾
(4)二分查找算法
二分查找算法是一種在有序數組中查找某一特定元素的搜索算法。搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜 素過程結束;
如果某一特定元素大于或者小于中間元素,則在數組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數組 為空,則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半,時間復雜度為Ο(logn) 。
(5)BFPRT(線性查找算法)
BFPRT算法解決的問題十分經典,即從某n個元素的序列中選出第k大(第k小)的元素,通過巧妙的分 析,BFPRT可以保證在最壞情況下仍為線性時間復雜度。該算法的思想與快速排序思想相似,當然,為使得算法在最壞情況下,依然能達到o(n)的時間復雜 度,五位算法作者做了精妙的處理。
算法步驟:
步驟1將n個元素每5個一組,分成n/5(上界)組。
步驟2取出每一組的中位數,任意排序方法,比如插入排序。
步驟3遞歸的調用selection算法查找上一步中所有中位數的中位數,設為x,偶數個中位數的情況下設定為選取中間小的一個。
步驟4用x來分割數組,設小于等于x的個數為k,大于x的個數即為n-k。
步驟5若i==k,返回x;若i《k,在小于x的元素中遞歸查找第i小的元素;若i》k,在大于x的元素中遞歸查找第i-k小的元素。終止條件:n=1時,返回的即是i小元素。
以上就是編程算法的全部內容,相信看完大家都應該明白了“編程算法是什么”。這些都是編程的基礎知識,大家一定要掌握哦!
編輯:jq
-
編程
+關注
關注
88文章
3614瀏覽量
93686
原文標題:初學編程:算法編程是什么意思?盤點最常用的 5 大算法!
文章出處:【微信號:cyuyanxuexi,微信公眾號:C語言編程學習基地】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論