這是我學習python后學習的第一個排序算法。

排序需要關注兩個維度，一是時間復雜度，二是穩(wěn)定性。

冒泡排序的時間復雜度為O（n^2）；屬于穩(wěn)定排序算法。

冒泡排序原理：有一個無序數組（A，下標為i,元素個數為n），要對無需數組進行排序。第一輪比較：第一步開始進行相鄰兩個元素的對比，若第1個位于第2位，交換他們的位置；第二步，用剛才比較大的那個數字和第3位數比較，誰大誰就在第3位。。。以此類推，直至最大的數放在最后一位。第二輪比較：重復第一輪的方法，直至第n-1輪（即len(A[i])-1）輪比較，此時我們便得到了一個有序的數組。

優(yōu)化方案：從上邊的原理可以看出，冒泡排序每輪比較都需要進行n-1次兩兩比較；但是我們可以知道，每做完一輪比較，最后一個位置的數就已經定下來了，所以，我們可以在后續(xù)每輪的比較中，減少一次兩兩比較。

好啦，準備工作已說完，python源碼現身：

# coding:utf-8

# 冒泡排序

defpaopao(A):

? ? print A

for i in range(len(A)-1,0,-1): ? ?# 外層循環(huán)是要比較的次數

? ? print i

? ? for j in range(i): ? ?# 內層循環(huán)是兩兩比較,交換

? ? ? ? if A[j] > A[j+1]:

? ? ? ? ? ? A[j],A[j+1] = A[j+1],A[j]# python特有的交換兩個元素的公式

? ? ? ? ? ? # max1 = A[j]

? ? ? ? ? ? # A[j] = A[j+1]

? ? ? ? ? ? # A[j+1] = max1

? ? ? ? print A

if__name__ =="__main__":

? ? s = [8,6,7,4,2,3,5]

? ? # 打印原數組

? ? print s

? ? # 打印排序后的數組

? ? paopao(s)

? ? print s