排序演算法 冒泡排序
重磅乾貨，第一時間送達
導言
排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。排序演算法有很多，本文將介紹最經典的排序演算法：冒泡排序，並分別利用C++和Python進行實現。
排序
排序的定義
假設含有n個記錄的序列為，其相應的關鍵字分別是，需要確定1,2,...,n的一種排列p1,p2,...,pn，使其相應的關鍵字滿足kp1
簡單來說，排序就是使輸入的序列變成符合一定規則（關鍵字）的有序序列（非遞減或非遞增）。大多數遇到的排序問題都是按數據元素值的大小規則進行排序的問題。所以本文為了方便起見，只討論數據元素值大小比較的排序問題。
排序的穩定性
假設ki=kj（1
如果排序後ri仍領先於rj，則稱所用的排序方法是穩定的；
反之，若可能使得排序後的序列中rj領先於ri，則稱所用的排序方法是不穩定的。
簡單來概括穩定和不穩定[2]：
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b前面；
不穩定：如果a原本在b前面，而a=b，排序之後a可能在b的後面。
時間和空間複雜度
時間複雜度：對排序數據的總的操作次數。反應當n變化時，操作次數呈現什麼規律
空間複雜度：演算法在計算機內執行時所需要的存儲空間的容量，它也是數據規模n的函數。
常見的排序演算法
冒泡排序（Bubble Sort）
基本思想
比較相鄰的兩個元素，將值大的元素交換到右邊（降序則相反）
步驟：
比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
針對所有的元素重複以上的步驟，除了最後一個；
重複步驟1~3，直到排序完成。
比如有n個元素，那麼第一次比較迭代，需要比較n-1次（因為是相鄰成對比較，最後一個元素沒有與下一個相鄰比較的對象，所以是n-1次），此次迭代完成後確定了最後一個元素為最大值；第二次比較迭代，需要比較n-2次，因為第一次迭代已經確定好了最後一個元素，所以不再需要比較；...；第 i次比較迭代，需要比較n-i次，此時確定後面i個元素是有序的較大元素；...；第n-1次比較迭代，需要比較n-(n-1)次，此時完成冒泡排序操作。
時間複雜度：o(n^2) = (n-1)*(n-1)
動圖演示：
過程演示：
待排序數組：，升序排序
---------------------------------------
第一次循環：
第一次比較5和4，5>4，交換位置：
第二次比較5和7，5
第三次比較7和1，7>1，交換位置：
第四次比較7和6，7>6，交換位置：
第五次比較7和2，7>2，交換位置：
第一次循環完成結果：
----------------------------------------
第二次循環：
第一次比較4和5，4
第二次比較5和1，5>1，交換位置：
第三次比較5和6，5
第四次比較6和2，6>2，交換位置：
第五次比較6和7，6
第二次循環完成結果：
----------------------------------------
第三次循環：
第一次比較4和1，4>1，交換位置：
第二次比較4和5，4
第三次比較5和2，5>2，交換位置：
第四次比較5和6，5
第五次比較6和7，6
第三次循環完成結果：
----------------------------------------
第四次循環：
第一次比較1和4，1
第二次比較4和2，4>2，交換位置：
第三次比較4和5，4
第四次比較5和6，5
第五次比較6和7，6
第三次循環完成結果：
----------------------------------------
第五次循環：
第一次比較1和2，1
第二次比較2和4，2
第三次比較4和5，4
第四次比較5和6，5
第五次比較6和7，6
第三次循環完成結果：
相信看完上面的演示過程，你對冒泡排序過程及原理有了完全的理解，但是細心的朋友應該會發現其實在第四次循環就已經得到了最終的結果，這麼來看第五次循環完全是多餘的，於是就有冒泡排序的改進版本：當某一輪循環當中沒有交換位置的操作，說明已經排好序了，就沒必要再循環了，break退出循環即可。
複雜度分析：
時間複雜度：若給定的數組剛好是排好序的數組，採用改進後的冒泡排序演算法，只需循環一次就行了，此時是最優時間複雜度：O(n)，若給定的是倒序，此時是最差時間複雜度：O(n^2) ，因此綜合平均時間複雜度為：O(n^2)
空間複雜度：因為每次只需開闢一個temp的空間，因此空間複雜度是：O(1)
代碼實現
C++代碼
Python代碼
參考
2 https://zhuanlan.zhihu.com/p/37077924
3 https://www.cnblogs.com/onepixel/p/7674659.html
TAG:CVer |