閱讀更多

2頂
0踩

行業應用

轉載新聞 趣味算法圖解,文科生都看懂了

2018-04-17 11:19 by 副主編 jihong10102006 評論(4) 有42624人瀏覽
編者按

IDEA 是由 SándorP. Fekete、Sebastian Morr 和 Sebastian Stiller 共同推出的圖解算法系列。 它們最初是為 Sándor 在德國不倫瑞克工業大學開設的算法和數據結構講座而設計的,作者希望它們能夠有更廣的用途,因此在網上發布了這個項目,希望能夠幫助到教師、學生和有好奇心的人們。算法將會不斷更新,可以訪問頁面了解更多信息:https://idea-instructions.com/。

這些圖片使用 Inkscape 繪制,可以使用任意一款向量圖編輯軟件來編輯它們。每個算法下面都有相應的圖片下載地址。

快速排序

快速排序是一種“分而治之”的排序算法,通過隨機選擇“分區點”來避免出現最壞的情況。

  • 隨機選擇“分區點”。
  • 按照“分區點”的高度劃條線。
  • 高出“分局點”的元素需要向右移動。
  • 低于“分區點”的元素需要向左移動。
  • 移動元素。
  • 重復上述的步驟分別對位于“分區點”兩邊的元素進行排序
。 下載地址:https://idea-instructions.com/quick-sort/

Bogo 排序

Bogo 排序也被稱為“愚蠢的排序”,是一種非常簡單但低效的排序算法,就是不斷打亂元素的順序,直到達到有序為止。

  • 查看元素是否有序。
  • 元素無序,那么就打亂順序。
  • 再次檢查元素是否有序。
  • 如果有序,排序成功,否則繼續重復上述步驟。
下載地址:https://idea-instructions.com/bogo-sort/

二分查找

二分查找是一種快速從一個有序數組中找到某個元素位置的查找算法。這有點類似于猜數字游戲,通過不斷問“目標數字是大于還是小于某個數”這樣的問題,最終猜出目標數字。

  • 限定元素區間。
  • 待查找元素在區間的某個位置嗎?
  • 不在。
  • 那么看看待查找元素是不是在當前位置的左邊或者右邊。
下載地址:https://idea-instructions.com/binary-search/

歸并排序

歸并排序也是一種“分而治之”的遞歸排序算法。

  • 把元素分成兩部分,對每一個部分采用遞歸的歸并排序。
  • 比較已經排好序的元素。
  • 合并已經排好序的元素。
  • 排序完畢。
下載地址:https://idea-instructions.com/merge-sort/

平衡二叉樹

平衡二叉樹是自平衡的二叉樹變種,可以保證快速的查找、插入和刪除操作。


以圖中的平衡二叉樹為例:
  • 左子節點比父節點小,而父節點比右子節點小。如果根節點左右子樹的高度差超過 1,就變得不平衡。
  • 想知道樹中是否包含了元素 11?11 比 10 大,那么就查找 10 的右子節點 12。11 比 12 小,所以就查找 12 的左子節點,12 的左子節點剛好是要查找的 11。同樣的,樹中是否包含了元素 8?8 比 10 小,那么就查找 10 的左子節點 6。8 比 6 大,那么就查找 6 的右子節點。6 的右子節點不存在,說明樹中不存在元素 8。
  • 如何找到樹中最小的元素?從根節點開始,一直順著左子節點,找到最后一個葉子節點就是樹中最小的元素。
  • 如何找到 10 的下一個元素?如果根節點剛好是 10,那么就從 10 的右子樹中找到最小的那個元素。如果根節點不是 10,那么先找到 10,如果 10 沒有右子節點,那么就一直往父節點找,直到找到比 10 大的元素為止。
  • 在樹種加入 17 或刪除 10,破壞了樹的平衡,這個時候需要通過旋轉恢復樹的平衡。
下載地址:https://idea-instructions.com/avl-tree/

圖遍歷

圖遍歷算法會遍歷圖中所有可達的頂點,可以通過輔助數據結構來實現各種遍歷,比如使用無序集合實現隨機遍歷,使用堆棧實現深度優先遍歷,使用隊列實現廣度優先遍歷。

  • 隨機查找:選定一個頂點,把它放入一個無序集合中。從集合中取出一個頂點,訪問該頂點,把該頂點的相鄰頂點放入集合中,并把該頂點移出集合。重復這一過程,直到集合中的元素全部被遍歷完畢。
  • 深度優先遍歷:選定一個頂點壓入棧中,把該頂點其中的一個相鄰頂點也壓入棧中。訪問棧頂的頂點,如果該頂點沒有其他相鄰的頂點,就出棧。如果有其他相鄰頂點,就把其中的一個相鄰頂點壓入棧中。重復這一過程,直到棧中的元素全部被遍歷完畢。
  • 廣度優先遍歷:選定一個頂點,把該頂點的相鄰頂點放進隊列尾部。訪問隊列頭部的頂點,把該頂點移出隊列,如果該頂點有相鄰頂點,就把相鄰頂點放進隊列尾部。重復這一過程,直到隊列中的元素全部遍歷完畢。
下載地址:https://idea-instructions.com/graph-scan/

一筆畫

一筆畫是一種 Fleury 算法,旨在優雅地找出圖中的歐拉(Eulerian)路徑。歐拉路徑是圖中的一條路徑,剛好經過每條邊,并且每條邊只被訪問一次。

  • 頂點度數表示該頂點有幾條邊。
  • 如果圖中有且僅有兩個頂點的度數為奇數,其他為偶數,或者不存在奇數度數的頂點,則存在歐拉路徑。
  • 選定一個頂點開始畫路徑。
  • 如果存在兩個以上的橋,那么可以走橋。如果只剩下一個橋,就不能走橋,除非只剩下橋可以走。
  • 如果還有沒有走過的邊,重復步驟 4。
  • 成功畫出歐拉路徑。
下載地址:https://idea-instructions.com/euler-path/
原文鏈接:https://idea-instructions.com/
  • 大小: 85 KB
  • 大小: 68.4 KB
  • 大小: 90 KB
  • 大小: 73.9 KB
  • 大小: 113.6 KB
  • 大小: 89.9 KB
  • 大小: 121.8 KB
  • 大小: 110.2 KB
來自: InfoQ
2
0
評論 共 4 條 請登錄后發表評論
4 樓 mmmzzc 2018-07-02 16:51
果然文如標題啊~
文科生能看懂,我這個寫了幾年代碼的碼農,文學素養不夠,真心看不懂~
3 樓 Miaonly 2018-04-20 09:50
圖很形象,容易懂
2 樓 somefuture 2018-04-19 13:12
畫的太有意思了
1 樓 jy03100000 2018-04-17 20:09
我個寫bug的都看不懂

發表評論

您還沒有登錄,請您登錄后再發表評論

相關推薦

Global site tag (gtag.js) - Google Analytics