冒泡排序
核心算法
在数组x[n]中，从第一个数开始，拿x[i]和后面的数x[i+1]进行比较，如果x[i]比后面的大，就交换两个数的位置，这样遍历一遍数组后，把最大的数据排在了最后面，之后继续循环排剩下的n-1个数，直到完成所有的排序，由于每次都是把最大的排到最后面，就好像冒泡一样，故取名冒泡排序。
分解实现过程
数列：12 23 34 2 31
方法：
遍历一遍数列，相邻两个数比较，如果前面的比后面的大，就交换位置。
第一次遍历数列过程如下：
第1次比较：12 23
因为12比23小所以不必交换位置，数列为12 23 34 2 31
第2次比较：23 34
因为23比34小所以不必交换位置，数列为12 23 34 2 31
第3次比较：34 2
因为34比2大所以需要交换位置，交换后数列为12 23 2 34 31
第4次比较：34 31
因为34比31大所以需要交换位置，交换后数列为12 23 2 31 34
所以
第一次遍历后的结果是：12 23 2 31 34
练习1：写出每一次遍历后的结果
第一次遍历：12 23 2 31 34
第二次遍历：12 2 23 31 34
第三次遍历：2 12 23 31 34
第四次遍历：2 12 23 31 34
练习2：一个数组有n个元素，需要遍历几次才能得到排序结果
n-1次
因为每一次是用相邻两个元素比较，所以就是n-1次。
代码实现冒泡排序
因为每一次遍历都需要相邻两个数比较，所以需要写两层循环。第一层循环是总的遍历次数，第二层循环是相邻两个数比较。需要考虑每次遍历比较时，比较的下标都是从0开始，但是不是每次都要比较完整个数列。
代码：
#coding=utf-8
def bubbleSort(listx):
print "初始化数组为：%s" % (listx)
xLen = len(listx)
for i in xrange(xLen-1):
for j in xrange(xLen-1-i):
if listx[j] > listx[j+1]:
listx[j],listx[j+1] = listx[j+1],listx[j]
print "第%s次排序结果：%s" % (i + 1, listx)
return listx
运行结果:
初始化数组为：[343, 3454, 4, 5, 7]
第1次排序结果：[343, 4, 5, 7, 3454]
第2次排序结果：[4, 5, 7, 343, 3454]
第3次排序结果：[4, 5, 7, 343, 3454]
第4次排序结果：[4, 5, 7, 343, 3454]
[4, 5, 7, 343, 3454]
练习3：for j in xrange(xLen-1-i) 修改成 for j in xrange(xLen-1),功能是否正确，弊端在哪里
不影响最终排序结果
弊端是排序过程会产生无用的比较次数，因为有些元素没有必要再去比较了。
练习4：修改程序，使得结果按从大到小排序
# coding=utf-8
def bubbleSort(listx):
xLen = len(listx)
for i in xrange(xLen-1):
for j in xrange(xLen-1-i):
if listx[j] < listx[j+1]:
listx[j],listx[j+1] = listx[j+1],listx[j]
return listx
if __name__ == '__main__':
print bubbleSort([32,34,1,3,45])
D:\ >python 32.py
[45, 34, 32, 3, 1]
练习5：针对一个数组x[n]进行冒泡排序，需要比较多少次
(n-1)+(n-2)+(n-3)+...+1
第一次比较：n-1次
第二次比较：n-2次
……
第n-1次比较：1次
一共：n-1+n-2+....+1
=n(n-1)/2
=n^2/2-n/2
时间复杂度
1、什么是复杂度？
用程序去做某一件事情，消耗的计算次数。
计算次数越少效率越高，反之效率越低。
2、时间复杂度的表示
时间复杂度使用大写的o表示，即O，然后是括号，括号里是项式。
一般时间复杂度从小到大的排序为（时间复杂度越小效率越高）：
O(1)<O(logn)<O(nlogn)<O(n^2)<O(n^3)...<O(2^n)<O(n!)
logn，以2为底数
3、时间复杂度的项式是怎么得到的？
(1) 得到算法的计算次数（一般是等差数列或等比数列，找到其通项公式。）
(2) 把计算次数中，保留最大的项式，去掉其他项式
(3) 把最大项式的因子去掉
(4) 匹配上述公式，得到O表示的时间复杂度
练习6：冒泡排序的时间复杂度是多少？
O(n^2)
怎么得到的？
我们上面所求得的n(n-1)/2，可拆解为n^2/2-n/2
保留最大的项式，去掉其他项式，即去掉n/2
把最大项式的因子去掉（保留最大的影响因子），即去掉2
其时间复杂度，最大的影响因子是n^2，故其时间复杂度O(n^2)
