python排序算法 ——冒泡排序

---

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

• python排序算法 ——冒泡排序
• 一、前言
• 二、算法描述
• 三、代碼實現
• 總結

---

一、前言

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

二、算法描述

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

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

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

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

接下來遍歷到的是第二個元素。如圖2-16所示，此時第二個元素的值已經變為5。把它和它后方的元素6對比，發現5和6的排列順序已經是正確的（前面的數小于后面的數），這時候不用交換這兩個元素的值，直接繼續遍歷。

如圖2-17所示，遍歷到第三個元素時，發現它比后面的元素更大，這時，繼續交換這兩個元素的值。

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

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

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

但是，我們發現，在排好第5個數之后，整個數組的排序就已經完成了，在接下來的遍歷中不會再產生元素的交換。這時，我們可以直接結束遍歷。

三、代碼實現

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

冒泡排序的代碼：

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

運行程序，輸出結果為：

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

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

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

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

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

---

總結

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

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

本文題目：python排序算法——冒泡排序（附代碼）-創新互聯
轉載來源：http://vcdvsql.cn/article32/cedjpc.html

成都網站建設公司_創新互聯，為您提供關鍵詞優化、響應式網站、全網營銷推廣、面包屑導航、靜態網站、域名注冊

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯