排序算法之冒泡排序
2020-06-13 本文已影响0人
焰火青春
冒泡排序（Bubble Sort）是一种比较简单的排序算法，它会重复地遍历要排序的数列，一次比较两个元素，若两者顺序错误则交换，直至没有再交换的为止。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
交换过程图示
image
a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
a[0] > a[1] a[0], a[1] = a[1], a[0] a = [26, 54, 93, 17, 77, 31, 44, 55, 20]
a[1] < a[2] 不交换 a = [26, 54, 93, 17, 77, 31, 44, 55, 20]
a[2] > a[3] a[2], a[3] = a[3], a[2] a = [26, 54, 17, 93, 77, 31, 44, 55, 20]
a[1] > a[2] a[1], a[2] = a[2], a[1] a = [26, 17, 54, 93, 77, 31, 44, 55, 20]
a[0] > a[1] a[0], a[1] = a[1], a[0] a = [17, 26, 54, 93, 77, 31, 44, 55, 20]
a[3] > a[4] a[3], a[4] = a[4], a[3] a = [17, 26, 54, 77, 93, 31, 44, 55, 20]
代码实现
def bubble_sort(alist):
n = len(alist)
# 外层循环 n-1 此，即循环到 n-2 为止
for j in range(n-1):
# 内层循环
for i in range(0, n-1-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(alist)
bubble_sort(alist)
print(alist)
分析
# 假设要排序的数列是 L
L = [54, 26, 93]
# 从左至右，分别为外层循环，内层循环
j=0, range(0, 2)
i=0 26, 54, 93 # 交换（54 比 26 大）
i=1 26, 54, 93 # 不交换
j=1，range(0, 1)
i=0 26, 54, 93 # 不交换
运行结果如下：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
优化
若数列本身是按从小到大排列的，那么：
def bubble_sort(alist):
n = len(alist)
# 外层循环 n-1 此，即循环到 n-2 为止
for j in range(n-1):
# 内层循环
count = 0
for i in range(0, n-1-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1 # 若上面交换了，就会执行这句，count 加一
if 0 == count:
return
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(alist)
bubble_sort(alist)
print(alist)
时间复杂度
- 最优时间复杂度：
O(n)，遍历一次发现没有任何可以交换的元素，排序接收 - 最坏时间复杂度：
O(n^2) - 稳定性：稳定
数列本身是有序的，那么就不会交换，count 始终皆为 0。若中间有交换则 count 不为零，即数列不有序，因此冒泡排序最好时间复杂度为 O(1)，即当数列有序时。最差时间复杂度为 o(n^2)。
