交换排序之冒泡排序

算法与数据结构

意识：python 讲究简洁，在开发中完全没有必要用 python 实现排序来服务开发，它有自己的排序函数 sorted()，所以 python 写排序算法，只是纯粹地实现。

1. 伪代码

——《算法导论》

2. Python 实现

注：冒泡排序的循环语句有多种写法。在代码细节上有些许差别，是因为操作元素的方法有些许差别（伪代码是从右往左冒泡，将小值移到左侧；下文的 python 实现是从左往右冒泡，将大值移到右侧。最后都实现了从小到大排序），但原理一致。

def bubble_sort(A):
    for i in range(len(A) - 1): # 冒泡趟数
        for j in range(len(A) - 1 - i): # 每次冒泡的比较次数
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

3. 时间复杂度

最坏情况是，原序列和你想要得到的序列相比，排序方式完全相反，此时，冒泡算法要执行所有的比较和交换，所以时间复杂度为

算法可以在原基础上改进。想象一个场景，为了简单，你不考虑原序列的顺序，而是对所有输入的序列都使用冒泡排序，这样只需要关注输出。那么，如果原序列的顺序符合你的要求，它理应不需要执行全部的比较和交换，即在第一次循环后只要发现没有元素交换过，我们就能确定原序列顺序符合要求，停止排序算法。

改进后：

def bubble_sort(A):
    for i in range(len(A) - 1):
        exchange = false
        for j in range(len(A) - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]
                exchange = True
        if not exchange: # 没有交换过，说明原序列已经有序。退出算法
            break

那么，此算法的最好情况的时间复杂度变为：