閱讀更多

2頂
0踩

行業應用

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

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

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 真人娱乐官方网站 辽阳市| 呼和浩特市| 普兰店市| 阳高县| 玉溪市| 克拉玛依市| 吴忠市| 宁化县| 阿拉尔市| 仙居县| 云霄县| 盐池县| 合阳县| 都安| 大新县| 宁波市| 甘洛县| 常熟市| 公主岭市| 湖州市| 湖口县| 孝感市| 沧源| 比如县| 四会市| 新安县| 土默特右旗| 广南县| 花莲市| 都匀市| 密山市| 中西区| 静安区| 工布江达县| 德阳市| 北京市| 德州市| 莆田市| 青河县| 满洲里市| 封丘县| 灵石县| 江门市| 营山县| 屯昌县| 新疆| 大理市| 华阴市| 丰城市| 永城市| 嘉祥县| 兴国县| 丰镇市| 郑州市| 保亭| 西丰县| 元氏县| 台江县| 通辽市| 思茅市| 珠海市| 宿松县| 大洼县| 扶绥县| 临汾市| 长岭县| 城口县| 金川县| 霍林郭勒市| 太仓市| 邵阳市| 吉首市| 襄樊市| 英德市| 澄江县| 邯郸市| 依兰县| 上蔡县| 南宫市| 湟中县| 珠海市| 庆元县| 辽宁省| 万安县| 楚雄市| 嘉祥县| 关岭| 扬州市| 孟村| 安泽县| 隆昌县| 内丘县| 崇文区| 诏安县| 镇安县| 苍山县| 灵璧县| 于都县| 怀宁县| 长子县| 施秉县| 淅川县| 墨竹工卡县| 扶绥县| 山西省| 左贡县| 北海市| 永平县| 石狮市| 重庆市| 新沂市| 阜阳市| 美姑县| 徐州市| 新田县| 祁东县| 钟祥市| 北海市| 从江县| 姜堰市| 黔南| 海晏县| 淮南市| 永济市| 靖宇县| 庆城县| 呼伦贝尔市| 扎囊县| 花垣县| 惠来县| 河北省| 中卫市| 清新县| 芜湖市| 青神县| 弥渡县| 新安县|