冒泡排序
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大星 的文章