本文為 AI 研習社編譯的技術部落格,原标題 :
A tour of the top 5 sorting algorithms with Python code
作者 | George Seif
翻譯 | 鄧普斯•傑弗
校對 | shunshun 整理 | 鳳梨妹
原文連結:
https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889
算法基礎:五大排序算法Python實戰教程
排序算法的複雜度
排序是每個軟體工程師和開發人員都需要掌握的技能。不僅要通過程式設計面試,還要對程式本身有一個全面的了解。不同的排序算法很好地展示了算法設計上如何強烈的影響程式的複雜度、運作速度和效率。
讓我們看一下前6種排序算法,看看如何在Python中實作它們!
冒泡排序
冒泡排序通常是在CS入門課程中教的,因為它清楚地示範了排序是如何工作的,同時又簡單易懂。冒泡排序步驟周遊清單并比較相鄰的元素對。如果元素順序錯誤,則交換它們。重複周遊清單未排序部分的元素,直到完成清單排序。因為冒泡排序重複地通過清單的未排序部分,是以它具有最壞的情況複雜度O(n^2)。
選擇排序
選擇排序也很簡單,但常常優于冒泡排序。如果您在這兩者之間進行選擇,最好預設選擇排序。通過選擇排序,我們将輸入清單/數組分為兩部分:已經排序的子清單和剩餘要排序的子清單,它們構成了清單的其餘部分。我們首先在未排序的子清單中找到最小的元素,并将其放置在排序的子清單的末尾。是以,我們不斷地擷取最小的未排序元素,并将其按排序順序放置在排序的子清單中。此過程将重複進行,直到清單完全排序。
插入排序
插入排序比冒泡排序和選擇排序既快又簡單。有趣的是,有多少人在玩紙牌遊戲時會整理自己的牌!在每個循環疊代中,插入排序從數組中删除一個元素。然後,它在另一個排序數組中找到該元素所屬的位置,并将其插入其中。它重複這個過程,直到沒有輸入元素。
歸并排序
歸并排序是分而治之算法的完美例子。它簡單地使用了這種算法的兩個主要步驟:
(1)連續劃分未排序清單,直到有N個子清單,其中每個子清單有1個“未排序”元素,N是原始數組中的元素數。
(2)重複合并,即一次将兩個子清單合并在一起,生成新的排序子清單,直到所有元素完全合并到一個排序數組中。
快速排序
快速排序也是一種分而治之的算法,如歸并排序。雖然它有點複雜,但在大多數标準實作中,它的執行速度明顯快于歸并排序,并且很少達到最壞情況下的複雜度O(n²) 。它有三個主要步驟:
(1)我們首先選擇一個元素,稱為數組的基準元素(pivot)。
(2)将所有小于基準元素的元素移動到基準元素的左側;将所有大于基準元素的元素移動到基準元素的右側。這稱為分區操作。
(3)遞歸地将上述兩個步驟分别應用于比上一個基準元素值更小和更大的元素的每個子數組。
喜歡嗎?
在Twitter上關注我,在那裡我釋出了最新最偉大的人工智能、技術和科學!
想要繼續檢視該篇文章相關連結和參考文獻?
長按連結點選打開或點選【算法基礎:五大排序算法python實戰教程】:
https://ai.yanxishe.com/page/TextTranslation/1374
AI研習社每日更新精彩内容,觀看更多精彩内容:雷鋒網(公衆号:雷鋒網)雷鋒網雷鋒網
AI/機器學習年度2018年度進展綜述
算法基礎:五大排序算法Python實戰教程
手把手:用PyTorch實作圖像分類器(第一部分)
手把手:用PyTorch實作圖像分類器(第二部分)
等你來譯:
對混亂的資料進行聚類
初學者怎樣使用Keras進行遷移學習
強化學習:通往基于情感的行為系統
一文帶你讀懂 WaveNet:谷歌助手的聲音合成器