前言

如果說各種各樣的編程語言是五花八門的招式，那么數(shù)據(jù)結(jié)構(gòu)和算法就是程序員的內(nèi)功了，這也是為什么各種招聘面試永遠不會冷落這些的原因。而排序作為數(shù)據(jù)結(jié)構(gòu)一個重要組成。所謂排序，就是將一組無序的數(shù)據(jù)整理成為有序的序列的過程。

排序分類

一般而言，排序分為內(nèi)部排序和外部排序。

• 若整個排序過程不需要訪問外存便能夠完成，這類排序稱為內(nèi)部排序。
• 若數(shù)據(jù)量很大，排序不可能在內(nèi)存中完成，這類排序稱為外部排序。

冒泡排序

冒泡排序是一種交換排序，交換排序的基本思想是：兩兩比較待排序的關(guān)鍵字，并交換不滿足次序要求的那對數(shù)，直到整個序列都滿足次序要求為止。

什么是冒泡排序

• 以升序為例，對n個數(shù)據(jù)，共進行n輪排序，每一輪兩兩比較相鄰元素，將小的放到前面大的放到后面，每一輪結(jié)果是將當前最大的元素移動到序列最后。
• 由于每一輪排序當前最大的元素到達序列的最底部，越小的元素慢慢浮動到序列的頂部，故名冒泡排序。

代碼實現(xiàn)

這個排序?qū)崿F(xiàn)并不是很難，用Python實現(xiàn)如下。

def bubble_sort(data):for i in range(len(data)-1):print("第{}趟排序".format(i))for j in range(len(data)-1-i):if data[j] > data[j+1]:data[j], data[j+1] = data[j+1], data[j]print("當前排序結(jié)果為:", data)return Nonetest_data = [1, 3, 5, 7, 9, 8, 6, 4, 2] print("原來數(shù)據(jù)", test_data) bubble_sort(test_data)

它有如下的執(zhí)行結(jié)果。

原來數(shù)據(jù) [1, 3, 5, 7, 9, 8, 6, 4, 2] 第0趟排序 當前排序結(jié)果為: [1, 3, 5, 7, 8, 6, 4, 2, 9] 第1趟排序 當前排序結(jié)果為: [1, 3, 5, 7, 6, 4, 2, 8, 9] 第2趟排序 當前排序結(jié)果為: [1, 3, 5, 6, 4, 2, 7, 8, 9] 第3趟排序 當前排序結(jié)果為: [1, 3, 5, 4, 2, 6, 7, 8, 9] 第4趟排序 當前排序結(jié)果為: [1, 3, 4, 2, 5, 6, 7, 8, 9] 第5趟排序 當前排序結(jié)果為: [1, 3, 2, 4, 5, 6, 7, 8, 9] 第6趟排序 當前排序結(jié)果為: [1, 2, 3, 4, 5, 6, 7, 8, 9] 第7趟排序 當前排序結(jié)果為: [1, 2, 3, 4, 5, 6, 7, 8, 9]

顯然，分析冒泡排序的算法復雜度如下。

排序名稱最好情況最壞情況平均情況

冒泡排序	O(n)	O(n^2)	O(n^2)

也就是說，這個算法是可以優(yōu)化的，一旦序列基本有序，只需要進行少數(shù)輪次排序就可以實現(xiàn)，后面的輪次是多余的，這也是很多面試官喜歡問到的。

優(yōu)化后的代碼如下所示，只有添加一個flag監(jiān)控該趟是否交換，一旦某一趟排序沒有交換，就認為排序可以結(jié)束了。

任何時候，在空間復雜度沒有太大優(yōu)化空間時，優(yōu)化時間復雜度是一個永恒不變的話題。

def bubble_sort_optimized(data):for i in range(len(data)-1):flag = Falseprint("第{}趟排序".format(i))for j in range(len(data)-i-1):if data[j] > data[j+1]:data[j], data[j+1] = data[j+1], data[j]flag = Trueif flag is False:breakprint("當前排序結(jié)果為:", data)return None test_data = [1, 2, 3, 4, 5, 6, 7, 9, 8] print("原來數(shù)據(jù)", test_data) bubble_sort_optimized(test_data)

它有如下的執(zhí)行結(jié)果。

原來數(shù)據(jù) [1, 2, 3, 4, 5, 6, 7, 9, 8] 第0趟排序 當前排序結(jié)果為: [1, 2, 3, 4, 5, 6, 7, 8, 9] 第1趟排序

更加詳細可以查看我的Github倉庫，歡迎star或者fork。

總結(jié)

以上是生活随笔為你收集整理的排序算法-01冒泡排序（Python实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。