一、概念及原理
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
排序的整个过程可以根据这个舞动算法生动形象的展现出来：http://video.tudou.com/v/XMjE3MzE5MDgzMg==.html?__fr=oldtd
二、python进行算法分析实现
这里使用顺序表来实现，链表的话区别在于交换方式不一样而已，与算法思想关系不大。首先在一个顺序表中，循环一次，就会找出一个最大值（或者最小值），放在最后,设顺序表长度为n，则比较次数为n-1次。

 for i in range(0, len(alist)- 1):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]

那么要循环n-1次就可以全部进行比较排序

 for j in range(len(alist)-1):
      for i in range(0, len(alist)- 1):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]

时间复杂度：
最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
最坏时间复杂度：O(n2)
稳定性：稳定

这里有没有可以优化的点呢？当然有
我们知道在每次循环之后，已经确定的最大值或者最小值放在最后就不用再比较了，也就是说每循环一次就可以少比较一次，例如从小到大排序：
第一次循环比较n-1次，确定最大的数放在最后
第二次循环只需要比较n-2次，最后那个已经确定最大了就不用比较了对吧
所以：
在每次循环之后都多减一：可以用外面循环的变量控制，用count记录比较次数

提示：return 返回的是元祖

def bubble_sort(alist):
    """冒泡排序"""
    count = 0
    for j in range(len(alist)-1):
        for i in range(0, len(alist) - j - 1):
            count += 1
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
    return alist,count

def main():
    listA = [2,5,8,4,9,5,1,4]
    listB = bubble_sort(listA)
    print(listB)
# ([1, 2, 4, 4, 5, 5, 8, 9], 28)

if __name__ == '__main__':
    main()

三、算法优化
冒泡其实在简单排序算法中是最好的，并且如果列表已经快排好序了，那么排序算法将会是更好的选择。
优化2：已经排好序就提前停止算法
我们可以设置一个flag，当循环一次发现一次都没比较了就可以停止算法了。
优化3：上面写的算法只适合比较number或者string类型，如果要比较对象呢，就不适合了，所有可以传入一个比较函数，将算法函数变成高阶函数，就更具有通用性。
优化4：我们知道上面的函数在运行完成之后，原来传进去的列表顺序就改变了，产生了副作用，那么我们是不是应该尽量减少副作用，以便原来的列表还可以进行其他操作。这里用切片。

def bubble_sort(alist, *, cmp=lambda x, y: x > y):  # 通用性增强，可以根据传入的数据类型进行比较比如对象（优化3--解耦合）
    """冒泡排序"""
    alist = alist[:] # 函数的设计尽量无副作用（side-effect） （优化4--切片）
    for j in range(len(alist)-1):
        flag = False   # 如果已经排好了，可以提前停止了（优化2--不做多余操作）
        for i in range(0, len(alist) - j - 1):    # 每次循环，就排好了一个元素，减少比较次数（优化1）
            if cmp(alist[i], alist[i + 1]):
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                flag = True
        if not flag:
            break
    return alist