python排序算法——冒泡排序（附代碼）-創(chuàng)新互聯(lián)

python排序算法 ——冒泡排序

---

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

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

---

一、前言

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

二、算法描述

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

冒泡排序的平均時間復雜度是O(n2)，最好情況下的時間復雜度是O(n)，最壞情況下的時間復雜度是O( n2 )?？臻g復雜度是O(1)。冒泡排序算法是一個穩(wěn)定的排序算法。冒泡排序的過程同樣可以用圖說明。我們的目標還是把無序數(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)生元素的交換。這時，我們可以直接結束遍歷。

三、代碼實現(xiàn)

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

冒泡排序的代碼：

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　　　　 #如果本趟遍歷沒有發(fā)生元素交換，直接跳出循環(huán)
print(nums)

運行程序，輸出結果為：

[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的元素。把遍歷范圍設為range(i-1)，訪問數(shù)組時才不會越界。另一個需要注意的點是交換元素的條件：num[j]>num[j+1]。注意不要把大于號寫成大于等于號。當這兩個元素相等時，為保留它們的原有相對位置，不要進行交換。如果把運算符寫成大于等于號，排序算法的穩(wěn)定性就被破壞了。

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

---

總結

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

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

本文題目：python排序算法——冒泡排序（附代碼）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://bm7419.com/article32/cedjpc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供關鍵詞優(yōu)化、響應式網(wǎng)站、全網(wǎng)營銷推廣、面包屑導航、靜態(tài)網(wǎng)站、域名注冊

廣告

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