冒泡排序（Bubble Sort）：
作為常見的排序算法之一望侈，主要思想是龄句，通過兩層遍歷比較相鄰兩數(shù)的大小，交換兩數(shù)的位置浩姥，在每次遍歷之后挑随，選出當(dāng)前無序List中最大的那個(gè)放置在當(dāng)前無序List最后，并將該最大值劃分給有序List中,無序List的長度則減1勒叠，直到無序List的長度為0兜挨，排序完成（從低->高排序?yàn)槔?/p>
Python 基本實(shí)現(xiàn):
# -*- coding: UTF-8 -*-
def Bubble(x):
#遍歷所有元素
for i in range(len(x)-1, 0, -1):
#對剩余的i個(gè)無序元素進(jìn)行遍歷，將最大值放到隊(duì)列最后
for j in range(i):
if x[j]>x[j+1]:
#python的這個(gè)兩數(shù)交換的寫法非常贊
x[j],x[j+1]=x[j+1],x[j]
print x
list = [31,45,4,44,33,5,2,68]
Bubble(list)
思考:
冒泡算法屬于交換排序中的一種眯分。
時(shí)間復(fù)雜度
(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n * n)
空間復(fù)雜度
輔助空間：O（1）
優(yōu)化算法：
# -*- coding: UTF-8 -*-
def Bubble(x):
#通過設(shè)置flag對冒泡算法進(jìn)行優(yōu)化拌汇，當(dāng)發(fā)現(xiàn)某次遍歷中沒有進(jìn)行元素交換，則說明剩下的元素已經(jīng)有序颗搂，則結(jié)束遍歷
flag = True
#遍歷所有元素
for i in range(len(x)-1, 0, -1):
if flag:
#初始設(shè)置flag=false 表示沒有交換
flag = False
#對剩余的i個(gè)無序元素進(jìn)行遍歷担猛，將最大值放到隊(duì)列最后
for j in range(i):
if x[j]>x[j+1]:
#python的這個(gè)兩數(shù)交換的寫法非常贊
x[j],x[j+1]=x[j+1],x[j]
flag = True
else:
break
print x
list = [31,45,4,44,33,5,2,68]
Bubble(list)
時(shí)間復(fù)雜度
平均情況：O（n * n）
最好情況：O（n）
最差情況：O（n * n）
遞歸實(shí)現(xiàn)
def bubble_recursive_sort(x):
for i in range(len(x)-1, 0, -1):
if x[i]<x[i-1]:
x[i],x[i-1]=x[i-1],x[i]
bubble_recursive_sort(x)
return x
