冒泡排序

你好，我是悅創(chuàng)。

冒泡排序是基礎(chǔ)排序。算法采用重復(fù)遍歷數(shù)組并依次比較相鄰元素的方法來排序。由于在冒泡算法進行排序的過程中，最大數(shù)或者最小數(shù)會慢慢“浮”到數(shù)組的末尾，所以算法由此命名。

冒泡排序的平均時間復(fù)雜度是O(n^2)O(n2)，最好情況下的時間復(fù)雜度是O(n)O(n), 最壞情況下的時間復(fù)雜度是O(n^2)O(n2)。空間復(fù)雜度是O(1)O(1)。冒泡排序算法是一個穩(wěn)定的排序算法。

冒泡排序的過程同樣可以用圖片說明。我們的目標還是把無序數(shù)組以從小到大的順序排列。

冒泡排序原理

首先，如下圖所示，我們從第一個數(shù)開始遍歷。將第一個數(shù)與它后面的元素進行對比，發(fā)現(xiàn)后面的元素比它小。

這時候，如圖15所示，我們需交換這兩個元素的值。

接下來遍歷到的是第二個元素。如圖16所示，此時第二個元素的值已經(jīng)變?yōu)?。把它和它后方的元素6對比，發(fā)現(xiàn)5和6的排列順序已經(jīng)是正確的（前面的數(shù)小于后面的數(shù)），這時候不用進行元素交換，直接繼續(xù)遍歷。

如圖17所示，遍歷到第三個元素時，發(fā)現(xiàn)它比后面的元素更大，這時候就繼續(xù)交換這兩個元素的值。

如圖18所示，在類似的一系列操作后，數(shù)組中的最大值被交換到了數(shù)組中的最后一個（第8個）位置上。

如圖19所示，這時候，我們可以確定末尾元素的值是正確的，所以接下來我們只需要對第1-7個位置上的元素再進行遍歷了。

在對第1-7個位置上的的元素進行遍歷之后，我們可以確定排在第7位的數(shù)。同理，在對第1-6個位置上的元素，第1-5個位置上的元素等進行遍歷后，我們可以確定數(shù)組中排在第6位，第5位的數(shù)等。冒泡排序的剩下過程如圖20所示。

但是，我們發(fā)現(xiàn)，在排好第五個數(shù)之后，整個數(shù)組的排序就已經(jīng)完成了，在接下來的遍歷中不會再產(chǎn)生元素的交換。這時候，我們可以直接結(jié)束遍歷。

冒泡排序代碼

了解了冒泡排序的流程之后，我們再來看看冒泡排序的代碼。

冒泡排序的代碼：

nums = [5,3,6,4,1,2,8,7]for i in range(len(nums),0,-1): #更新本趟遍歷確定的元素位置    flag = 0        #flag用于標記是否有元素交換發(fā)生    for j in range(i-1): #遍歷未排序的數(shù)組        if nums[j]>nums[j+1]:            nums[j],nums[j+1] = nums[j+1],nums[j]            flag = 1 #標記存在元素交換    if not flag:         break #如果本趟遍歷沒有經(jīng)歷元素交換，直接跳出循環(huán)         print(nums)

運行程序，輸出結(jié)果為：

[1,2,3,4,5,6,7,8]

這段冒泡排序的代碼中使用了兩個for循環(huán)。外層for循環(huán)中的i代表每一次遍歷后確定位置的元素的下標。

變量 flag 用于記錄是否有元素交換發(fā)生，初始為0，在遍歷開始后，一旦兩位元素進行交換，它的值就會變?yōu)?。

隨后，再用一個 for 循環(huán)對未排序數(shù)組進行遍歷。為什么遍歷的范圍是 range(i-1)？因為未排序數(shù)組的最后一個元素下標為 i，而我們在遍歷時要同時訪問下標為j和 j+1 的元素。把遍歷范圍設(shè)為 ?range(i-1)，訪問數(shù)組時才不會越界。另一個需要注意的點是交換元素的條件：num[j] > num[j+1]。注意不要把大于號寫成大于等于號。當這兩個元素相等時，為保留它們的原有相對位置，不要進行交換。如果把運算符寫成大于等于號，排序算法的穩(wěn)定性就被破壞了。

遍歷結(jié)束后，如果flag的值仍然是0，那么說明在整一次遍歷中沒有元素交換發(fā)生，也就是說，所有元素都是有序排列的。這時候就可以直接跳出循環(huán)，節(jié)省時間。

小結(jié)

初級排序算法至此結(jié)束了。掌握了初級排序算法之后，我們再進入高級排序算法的學(xué)習(xí)。

長按識別下方二維碼，和眾多位島民一起

把別人的頓悟，變成你的基本功

?花半秒鐘就看透事物本質(zhì)的人，
? 和花一輩子都看不清的人，
? 注定是截然不同的命運。