冒泡排序
一、过程解释：将一个列表lista按，lista中存有n个数字按从小到大的顺序进行排序。我们依次比较lista[i]和lista[i+1]，如果lista[i]大于ista[i+1]就将这两个数的位置交换，第一轮比较完成后，最大的数字会排到列表的最后。之后继续循环排剩下的n-1个数，直到完成所有的排序，由于每次都是把最大的排到最后面，就好像冒泡一样，故取名冒泡排序。

举例1： lista = [41,23,5,9,20]，对lista按从小到大的顺序进行排序。

冒泡排序手工比较的过程：

第一轮比较：41与23比较，41>23，位置交换；41再分别向后比较，并按大小规则确定是否交换位置

第一轮比较结果：23,5,9,20,41

第一轮比较完成后，可以看到43作为列表中最大的数字已经排到了lista的最后。

第二轮比较：23与5比较，23>5，位置交换；23在依次向后比较，比较到20时停下，我们第一轮已经确定41是最大的并且移到了最后

第二轮比较结果：5,9,20,23,41

第三轮比较：5与9比较，5<9,不做交换；9和20比较，9<20也不做互换

第三轮比较结果：5,9,20,23,41

第四轮比较：5与9做比较，5<9,不做交换

第四轮比较结果：5,9,20,23,41

到这里就已经完成了对整个lista的冒泡排序了。

举例2：

对listb=[12,32,23,34,2]按从小到大排序。

第一轮：12,23,32,2,34

第二轮：12,23,2,32,34

第三轮：12,2,23,32,34

第四轮：2,12,23,32,34

可以看出，对于一个含有n个元素的列表，冒泡比较多少次可以确保所有元素都被遍历到？答案是 n-1次

疑问：举例1到第二轮结束其实已经完成了对lista的排序，为什么后面还有第三轮、第四轮的比较呢？

答案：从算法的角度来讲，对含有n个元素的列表比较时，是需要比较n-1次，才能确保每一个元素都被遍历到。由于上面例子中的排列顺序特殊，所以我们会感觉后面的比较其实是没有变化的。

二、python冒泡排序算法：

#enconding = utf-8

def Bubble_Sort(listx):
#i确定比较次数
for i in xrange(len(listx)-1):
#j确定比较的是哪个元素
for j in xrange(len(listx)-1-i): #通过i确定比较到哪里
#我们可以这样去把所有元素每次都全部比较一轮，但其实是没有必要的,效率低。
#for j in xrange(len(listx)-1)：

if listx[j]>listx[j+1]:
listx[j],listx[j+1] = listx[j+1],listx[j]
return listx

if __name__ == ‘__main__’:
print Bubble_Sort([12,32,23,34,2])

三、冒泡排序的时间复杂度

时间复杂度的计算方法：

1、得到算法的计算次数
2、把计算次数中，保留最大的项式，去掉其它项式
3、把最大项式的因子去掉
4、匹配上述公式，得到O表示的时间复杂度

对于冒泡排序，我们来算一下一共比较了多少次

还是用上面的例子，对listb=[12,32,23,34,2]按从小到大排序。

第一轮：12,23,32,2,34  比较4次；即n=5，比较了n-1次

第二轮：12,23,2,32,34  比较3次；即n=5，比较了n-2次

第三轮：12,2,23,32,34  比较2次；

第四轮：2,12,23,32,34  比较1次

以此类推： 冒泡排序总计比较次数应该是  n-1 + n-2 + n-3 +……+3+2+1

我们对此等差数列进行求和，Sn=n(a1+an)/2，注意：上面的式子是到n-1项，所以带入等差数列求和公式 （n-1）*（1+n-1）/2 = n(n-1)/2

按照上面时间复杂度的计算方法，去掉其他项保留最大项，且最大的影响结果是n^2，因此结果是 n^2

故冒泡排序的时间复杂度为 O(n^2)