问题描述

??记得刚刚接触算法的时候觉得特别难以理解.最初接触的是冒泡排序 ?? 但是现在看一遍马上知道怎么回事,以及想到如何代码实现.

??就像是咕噜咕噜冒泡泡一样.每次都是最大的泡泡冒到最上面.查看动画是最好理解的算法的方式之一.请参看:冒泡排序动画演示

??关于冒泡排序的特性:冒泡排序的对比时间复杂度是O(n^2) 交换时间复杂度是O(n^2).最优的排序算法时间比较复杂度为O(logn)

??冒泡排序的适应性相对来说比较广泛.链式结构也可以使用.冒泡排序的优势是无需任何额外的储存开销.选择排序从排序思维上来说,则是冒泡排序的性能优化版本

方法一

def bubbleSort(alist):

    for pass_num in range(len(alist)-1,0,-1): # 比对次数
        for i in range(pass_num):
            if alist[i+1] <  alist[i]:
                alist[i],alist[i+1] = alist[i+1] ,alist[i]
    return alist

print(bubbleSort([21,312,321,321,54,654,423,12,32,312]))

方法一优化版本

优化的内容具体体现在 : 如果发现一轮比较当中,没有发生元素之间相互交换,则是意味着元素已经排序完毕.可以终止掉后面的排序循环.使用exchangs进行监控

def bubbleSort_II(alist): # 性能改进
    exchanges = True #进行监控的变量
    pass_num = len(alist) - 1
    while pass_num >0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if alist[i+1] <  alist[i]:
                exchanges = True
                alist[i],alist[i+1] = alist[i+1] ,alist[i]
        pass_num = pass_num -1
    return alist

print(bubbleSort([21,312,321,321,54,654,423,12,32,312]))

参考

• 陈斌老师的数据结构课程-中国大学MOOC

冒泡排序(使用Python描述)

原文：https://www.cnblogs.com/gtscool/p/12513656.html