冒泡排序

一、思路

1、在數(shù)組[0,n)上

2、從i=0開始，不斷比較list[i]與list[i+1],順序的話不做調整；逆序的話交換二者位置。

3、i+1

4、當i = n-2時，1次遍歷結束，最大值到了正確位置

5、在剩余數(shù)組中繼續(xù)進行上述遍歷過程

二、實現(xiàn)

嵌套代碼編寫過程中循環(huán)體，先用pass占位，減小思維復雜度

from sort_helper import test_sort,random_arraydef bubble_sort(array):"""冒泡排序的經典實現(xiàn)"""n = len(array)#子過程運行閉區(qū)間的右端點標記定義為i,范圍[n-1,1],轉換為適合while慣用區(qū)間為[n-1,0)i = n-1while i > 0:#子過程交換位置標記定義為j，范圍為[0,i-1]，轉換為適合while慣用區(qū)間為[0，i)#子過程運行區(qū)間為[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]j += 1i -= 1return arrayif __name__ == '__main__':array = random_array()test_sort('bubble_sort', bubble_sort, array)

三、優(yōu)化

• 冒泡排序的子過程沒有提前中斷機制（對比插入排序），所以子數(shù)組中每個元素都要遍歷，交換又比較耗時；最終，導致算法性能較低。

• 但是相比于其他排序算法，冒泡排序子過程中對子數(shù)組中每個元素與其后綴元素進行了比較，這個特殊的過程可以作為優(yōu)化點（選擇排序則無此優(yōu)勢）

• 優(yōu)化的數(shù)學依據(jù)：對于序列A,若任意Ai < Ai+1,則序列A有序

• 一旦判斷子過程有序，則終止全部循環(huán)！

#性能改進 def bubble_sort1(array):"""冒泡排序的經典實現(xiàn)"""n = len(array)#子過程運行閉區(qū)間的右端點標記定義為i,范圍[n-1,1],轉換為適合while慣用區(qū)間為[n-1,0)i = n-1while i > 0:stop = True#子過程交換位置標記定義為j，范圍為[0,i-1]，轉換為適合while慣用區(qū)間為[0，i)#子過程運行區(qū)間為[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]stop = Falsej += 1if stop:breaki -= 1return array #代碼改進 def bubble_sort2(array):"""冒泡排序的經典實現(xiàn)"""n = len(array)stop = False#子過程運行閉區(qū)間的右端點標記定義為i,范圍[n-1,1],轉換為適合while慣用區(qū)間為[n-1,0)i = n-1while i > 0 and not stop:stop = True#子過程交換位置標記定義為j，范圍為[0,i-1]，轉換為適合while慣用區(qū)間為[0，i)#子過程運行區(qū)間為[0,i]j = 0while j < i:if array[j] > array[j+1]:array[j],array[j+1] = array[j+1],array[j]stop = Falsej += 1i -= 1return array

測試用例

if __name__ == '__main__':array1 = random_array()array2 = array1[:]array3 = nearly_ordered_array(10000, 1)array4 = array3[:]array5 = random_array(10000,0,1)array6 = array3[:]test_sort('bubble_sort random_array', bubble_sort, array1)test_sort('bubble_sort1 random_array', bubble_sort1, array2)test_sort('bubble_sort nearly_ordered_array', bubble_sort, array3)test_sort('bubble_sort1 nearly_ordered_array', bubble_sort1, array4)print('大量重復元素')test_sort('bubble_sort ', bubble_sort, array5)test_sort('bubble_sort1 ', bubble_sort1, array6)

數(shù)組有序性越強，優(yōu)化效果越好

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的冒泡排序及其优化的全部內容，希望文章能夠幫你解決所遇到的問題。

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