算法基礎(chǔ)：五大排序算法Python實(shí)戰(zhàn)教程
2019-01-10 來源：raincent
排序算法的復(fù)雜度
排序是每個軟件工程師和開發(fā)人員都需要掌握的技能。不僅要通過編程面試，還要對程序本身有一個全面的理解。不同的排序算法很好地展示了算法設(shè)計上如何強(qiáng)烈的影響程序的復(fù)雜度、運(yùn)行速度和效率。
讓我們看一下前6種排序算法，看看如何在Python中實(shí)現(xiàn)它們!
冒泡排序
冒泡排序通常是在CS入門課程中教的，因?yàn)樗宄匮菔玖伺判蚴侨绾喂ぷ鞯�，同時又簡單易懂。冒泡排序步驟遍歷列表并比較相鄰的元素對。如果元素順序錯誤，則交換它們。重復(fù)遍歷列表未排序部分的元素，直到完成列表排序。因?yàn)槊芭菖判蛑貜?fù)地通過列表的未排序部分，所以它具有最壞的情況復(fù)雜度O(n^2)。
選擇排序
選擇排序也很簡單，但常常優(yōu)于冒泡排序。如果您在這兩者之間進(jìn)行選擇，最好默認(rèn)選擇排序。通過選擇排序，我們將輸入列表/數(shù)組分為兩部分：已經(jīng)排序的子列表和剩余要排序的子列表，它們構(gòu)成了列表的其余部分。我們首先在未排序的子列表中找到最小的元素，并將其放置在排序的子列表的末尾。因此，我們不斷地獲取最小的未排序元素，并將其按排序順序放置在排序的子列表中。此過程將重復(fù)進(jìn)行，直到列表完全排序。
插入排序
插入排序比冒泡排序和選擇排序既快又簡單。有趣的是，有多少人在玩紙牌游戲時會整理自己的牌!在每個循環(huán)迭代中，插入排序從數(shù)組中刪除一個元素。然后，它在另一個排序數(shù)組中找到該元素所屬的位置，并將其插入其中。它重復(fù)這個過程，直到?jīng)]有輸入元素。
歸并排序
歸并排序是分而治之算法的完美例子。它簡單地使用了這種算法的兩個主要步驟：
(1)連續(xù)劃分未排序列表，直到有N個子列表，其中每個子列表有1個“未排序”元素，N是原始數(shù)組中的元素數(shù)。
(2)重復(fù)合并，即一次將兩個子列表合并在一起，生成新的排序子列表，直到所有元素完全合并到一個排序數(shù)組中。
快速排序
快速排序也是一種分而治之的算法，如歸并排序。雖然它有點(diǎn)復(fù)雜，但在大多數(shù)標(biāo)準(zhǔn)實(shí)現(xiàn)中，它的執(zhí)行速度明顯快于歸并排序，并且很少達(dá)到最壞情況下的復(fù)雜度O(n²) 。它有三個主要步驟：
(1)我們首先選擇一個元素，稱為數(shù)組的基準(zhǔn)元素(pivot)。
(2)將所有小于基準(zhǔn)元素的元素移動到基準(zhǔn)元素的左側(cè);將所有大于基準(zhǔn)元素的元素移動到基準(zhǔn)元素的右側(cè)。這稱為分區(qū)操作。
(3)遞歸地將上述兩個步驟分別應(yīng)用于比上一個基準(zhǔn)元素值更小和更大的元素的每個子數(shù)組。
原標(biāo)題 ：A tour of the top 5 sorting algorithms with Python code
作者：George Seif 翻譯： 鄧普斯•杰弗
標(biāo)簽：
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
