python实现冒泡排序(Bubble sort)

冒泡排序算法的工作原理如下：

比较相邻的元素，如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这一轮比较结束后，排在最后的元素会是最大的数，此时可看做这个数被归为了这组数据中的有序部分，那么剩下还没排序的即为无序部分。
开始第二轮的比较，一直比到倒数第二个数，因为最后一个在上一轮已经冒泡冒到有序部分了。
对越来越少的无序部分中的元素重复下一轮冒泡，直到无序部分中的元素全部排到有序部分中。

图示为第一轮冒泡，把包含9（n）个元素的列表当中最大的数先排到最后，这样的操作最多进行8（n-1）轮：

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

下面是代码实现：

def bubble_sort(alist):
    n = len(alist)
    for j in range(n-1, 0, -1):  #j:要经过j轮冒泡，值为n-1, n-2, n-3, ..., 3, 2, 1
        for i in range(j):  #注意j是递减的，轮数越小，要操作的元素就越多，但每轮上限为j-1
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

测试：

if __name__ == "__main__":
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    bubble_sort(li)
    print(li)

运行一下：

[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

python实现冒泡排序(Bubble sort)

相关推荐