@gongsheng
2018-03-16T23:08:25.000000Z
字数 775
阅读 923
算法与数据结构
意识:python 讲究简洁,在开发中完全没有必要用 python 实现排序来服务开发,它有自己的排序函数 sorted(),所以 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]
最坏情况是,原序列和你想要得到的序列相比,排序方式完全相反,此时,冒泡算法要执行所有的比较和交换,所以时间复杂度为
算法可以在原基础上改进。想象一个场景,为了简单,你不考虑原序列的顺序,而是对所有输入的序列都使用冒泡排序,这样只需要关注输出。那么,如果原序列的顺序符合你的要求,它理应不需要执行全部的比较和交换,即在第一次循环后只要发现没有元素交换过,我们就能确定原序列顺序符合要求,停止排序算法。
改进后:
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
那么,此算法的最好情况的时间复杂度变为: