0
| 本文作者： AI研習(xí)社-譯站 | 2019-01-07 10:55 |
本文為 AI 研習(xí)社編譯的技術(shù)博客，原標(biāo)題 ：
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
算法基礎(chǔ)：五大排序算法Python實(shí)戰(zhàn)教程
排序算法的復(fù)雜度
排序是每個(gè)軟件工程師和開發(fā)人員都需要掌握的技能。不僅要通過編程面試，還要對程序本身有一個(gè)全面的理解。不同的排序算法很好地展示了算法設(shè)計(jì)上如何強(qiáng)烈的影響程序的復(fù)雜度、運(yùn)行速度和效率。
讓我們看一下前6種排序算法，看看如何在Python中實(shí)現(xiàn)它們！
冒泡排序通常是在CS入門課程中教的，因?yàn)樗宄匮菔玖伺判蚴侨绾喂ぷ鞯?，同時(shí)又簡單易懂。冒泡排序步驟遍歷列表并比較相鄰的元素對。如果元素順序錯(cuò)誤，則交換它們。重復(fù)遍歷列表未排序部分的元素，直到完成列表排序。因?yàn)槊芭菖判蛑貜?fù)地通過列表的未排序部分，所以它具有最壞的情況復(fù)雜度O(n^2)。
選擇排序也很簡單，但常常優(yōu)于冒泡排序。如果您在這兩者之間進(jìn)行選擇，最好默認(rèn)選擇排序。通過選擇排序，我們將輸入列表/數(shù)組分為兩部分：已經(jīng)排序的子列表和剩余要排序的子列表，它們構(gòu)成了列表的其余部分。我們首先在未排序的子列表中找到最小的元素，并將其放置在排序的子列表的末尾。因此，我們不斷地獲取最小的未排序元素，并將其按排序順序放置在排序的子列表中。此過程將重復(fù)進(jìn)行，直到列表完全排序。
插入排序比冒泡排序和選擇排序既快又簡單。有趣的是，有多少人在玩紙牌游戲時(shí)會(huì)整理自己的牌！在每個(gè)循環(huán)迭代中，插入排序從數(shù)組中刪除一個(gè)元素。然后，它在另一個(gè)排序數(shù)組中找到該元素所屬的位置，并將其插入其中。它重復(fù)這個(gè)過程，直到?jīng)]有輸入元素。
歸并排序是分而治之算法的完美例子。它簡單地使用了這種算法的兩個(gè)主要步驟：
（1）連續(xù)劃分未排序列表，直到有N個(gè)子列表，其中每個(gè)子列表有1個(gè)“未排序”元素，N是原始數(shù)組中的元素?cái)?shù)。
（2）重復(fù)合并，即一次將兩個(gè)子列表合并在一起，生成新的排序子列表，直到所有元素完全合并到一個(gè)排序數(shù)組中。
快速排序也是一種分而治之的算法，如歸并排序。雖然它有點(diǎn)復(fù)雜，但在大多數(shù)標(biāo)準(zhǔn)實(shí)現(xiàn)中，它的執(zhí)行速度明顯快于歸并排序，并且很少達(dá)到最壞情況下的復(fù)雜度O(n2) 。它有三個(gè)主要步驟：
（1）我們首先選擇一個(gè)元素，稱為數(shù)組的基準(zhǔn)元素(pivot)。
（2）將所有小于基準(zhǔn)元素的元素移動(dòng)到基準(zhǔn)元素的左側(cè)；將所有大于基準(zhǔn)元素的元素移動(dòng)到基準(zhǔn)元素的右側(cè)。這稱為分區(qū)操作。
（3）遞歸地將上述兩個(gè)步驟分別應(yīng)用于比上一個(gè)基準(zhǔn)元素值更小和更大的元素的每個(gè)子數(shù)組。
在Twitter上關(guān)注我，在那里我發(fā)布了最新最偉大的人工智能、技術(shù)和科學(xué)！
想要繼續(xù)查看該篇文章相關(guān)鏈接和參考文獻(xiàn)？
長按鏈接點(diǎn)擊打開或點(diǎn)擊【算法基礎(chǔ)：五大排序算法python實(shí)戰(zhàn)教程】：
https://ai.yanxishe.com/page/TextTranslation/1374
AI研習(xí)社每日更新精彩內(nèi)容，觀看更多精彩內(nèi)容：雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
等你來譯：
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
