冒泡排序

1、題目

假設有一個列表 list = [5,4,3,2,1]

要求：按從小到大的順序排序

2、分析

● 冒泡排序的思路

兩兩比較，互換位置，每一輪選出最大（小）的數放到列尾

● 圖解

① 第一輪比較

第一輪比較

② 第二輪比較

③ 第三輪比較

④ 第四輪比較

由於每一輪只選出 1 個最大數，當最後一輪只剩 2 個元素時，結束。

總共需要比較的輪數 = 列數 - 1

比較的次數 = 列元素的個數 - 1，由於每一輪會排除一個最大（小）數，比較的次數會依次減 1；

3、Python 方案

● Python 代碼：

● Python 結果：

4、冒泡排序的時間複雜度

從代碼中可以看出一共遍歷了

n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，

那麼時間複雜度是 O (N^2)。

5、冒泡排序優化

曾經，Python大星 參加一個面試，面試官突然給我一張紙和筆，讓我現場寫個冒泡排序。

so easy，冒泡排序是排序算法中最簡單的一個，三下五除二，我就交上答卷。面試官點了點頭，示意我的答案正確，但接下來問了我一個問題，就讓我回家等消息啦。

OS：冒泡排序還能優化？？？

例如：無序列表為[2,3,1,4,5]

按照之前的冒泡排序的邏輯：該列表需要進行 4 輪排序

但我們可以觀察到：

● 在第二輪排序後，整個列表已經達到要求了，後面的循環無意義

優化點：當第 N 輪 無元素交換位置，則退出循環

第一輪排序過程

第二輪排序過程

● 在第一輪後，我們可以觀察到只進行了一次交換，從 3 後的數字已經排好序，故第二輪的比較中，再比較3之後的數字沒有意義

優化點：找出每輪排序的邊界

優化代碼：

>>>

閱讀更多 Python大星 的文章

關鍵字: Python 列表 算法