演算法基礎：五大排序演算法Python實戰教程

本文為 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(n2) 。它有三個主要步驟：

（1）我們首先選擇一個元素，稱為數組的基準元素(pivot)。

（2）將所有小於基準元素的元素移動到基準元素的左側；將所有大於基準元素的元素移動到基準元素的右側。這稱為分區操作。

（3）遞歸地將上述兩個步驟分別應用於比上一個基準元素值更小和更大的元素的每個子數組。

在Twitter上關注我，在那裡我發布了最新最偉大的人工智慧、技術和科學！

想要繼續查看該篇文章相關鏈接和參考文獻？

長按鏈接點擊打開或點擊【演算法基礎：五大排序演算法python實戰教程】：

https://ai.yanxishe.com/page/TextTranslation/1374

AI研習社每日更新精彩內容，觀看更多精彩內容：雷鋒網雷鋒網雷鋒網

等你來譯：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！