python排序算法 ——冒泡排序

---

創(chuàng)新互聯(lián)長期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為陽信企業(yè)提供專業(yè)的網(wǎng)站設(shè)計制作、成都做網(wǎng)站，陽信網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。文章目錄

• python排序算法 ——冒泡排序
• 一、前言
• 二、算法描述
• 三、代碼實現(xiàn)
• 總結(jié)

---

一、前言

相關(guān)知識來自《python算法設(shè)計與分析》。初級排序算法是指幾種較為基礎(chǔ)且容易理解的排序算法。初級排序算法包括插入排序、選擇排序和冒泡排序3種。雖然它們的效率相對于高級排序算法偏低，但是在了解初級排序算法之后，再去學(xué)習(xí)相對復(fù)雜的高級排序算法會容易許多。本文介紹冒泡排序。

二、算法描述

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

冒泡排序的平均時間復(fù)雜度是O(n2)，最好情況下的時間復(fù)雜度是O(n)，最壞情況下的時間復(fù)雜度是O( n2 )。空間復(fù)雜度是O(1)。冒泡排序算法是一個穩(wěn)定的排序算法。冒泡排序的過程同樣可以用圖說明。我們的目標(biāo)還是把無序數(shù)組以從小到大的順序排列。

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

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

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

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

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

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

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

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

三、代碼實現(xiàn)

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

冒泡排序的代碼：

nums = [5,3,6,4,1,2,8,7]
for i in range(len(nums),0,-1):　　#更新本趟遍歷確定的元素位置
  flag = 0　　　　　　　　　　　#flag用于標(biāo)記是否有元素交換發(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 #標(biāo)記存在元素交換
  if not flag:
    break　　　　 #如果本趟遍歷沒有發(fā)生元素交換，直接跳出循環(huán)
print(nums)

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

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

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

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

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

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

---

總結(jié)

以上就是今天要講的內(nèi)容，本文介紹了冒泡排序的理論知識和代碼實現(xiàn)。冒泡排序的平均時間復(fù)雜度是O(n2)，最好情況下的時間復(fù)雜度是O(n)，最壞情況下的時間復(fù)雜度是O( n2 )。空間復(fù)雜度是O(1)。冒泡排序算法是一個穩(wěn)定的排序算法。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：python排序算法——冒泡排序（附代碼）-創(chuàng)新互聯(lián)
本文路徑：http://weahome.cn/article/cedjpc.html