什么是冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

图解冒泡排序

python 实现

class Sort:
    def bubble_sort(self,data):
        for i in range(len(data)-1,0,-1):
            flag = False
            for j in range(i):
                if data[j]>data[j+1]:
                    data[j],data[j+1] = data[j+1],data[j]
                    flag = True
            if not flag:
                break
        return data #有返回的原地排序

实现结果

if __name__=='__main__':
    test = Sort()
    L = [9,8,7,6,5,4,3,2,1,0]
    res = test.bubble_sort(L)
    res = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

时间空间复杂度分析

原始的冒泡排序的时间复杂度最好，平均，最差都为 $O(n^2)$O(n2)，而此时经过改良的冒泡排序最好情况下的时间复杂度为 $O(n)$O(n)。
原地排序，空间复杂度为 $O(n)$O(n)。

稳定性

显然冒泡排序算法稳定。