冒泡排序
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 算法 07 -- 歸并排序的奧秘