Python中的排序---冒泡法
2021-04-06 16:28
标签：变量 英语 简单的 range bubble 来源 play display 代码 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。此算法依次比较序列的两个元素的大小，如果元素的顺序错误，就交换其位置，直到序列的元素变得有序才停止遍历。 时间复杂度O(n²) 交换过程如下图： 图片来源：https://blog.csdn.net/u014745194 运行结果 运行结果：循环了36次 定义一个开关变量，当本次循环进来，发现根本不需要交换的时候，改变开关变量的值，直接进入下一次循环 运行结果 Python中的排序---冒泡法 标签：变量 英语 简单的 range bubble 来源 play display 代码 原文地址：https://www.cnblogs.com/zh-dream/p/13396549.html
代码1
升序
lst=[ [1,9,8,5,6,7,4,3,2], [1,2,3,4,5,6,7,8,9] ]
lst1=lst[0]
print(lst1)
length=len(lst1)
for i in range(length): ## 控制循环的次数，因为每一个数都需要做一次循环比较
for j in range(length-i-1): ## 因为是两两比较，所以要少一次遍历
if lst1[j] > lst1[j+1]: ## 以下代码逻辑，当索引j对应的值比j+1对应的值大时，将较大值j赋值给临时变量tmp，由于索引j+1的值小，所以向前移动，将其值赋值给索引j，临时变量（索引j）的值需要依次向后比较
tmp=lst1[j]
lst1[j]=lst1[j+1]
lst1[j+1]=tmp
print(lst1)
统计交换次数和循环次数
lst = [[1, 9, 8, 5, 6, 7, 4, 3, 2], [1, 2, 3, 4, 5, 6, 7, 8, 9]]
lst1 = lst[0]
print(lst1)
count = 0
count_swap = 0
length = len(lst1)
for i in range(length):
for j in range(length - i - 1):
count += 1 ## 统计循环次数
if lst1[j] > lst1[j + 1]:
tmp = lst1[j]
lst1[j] = lst1[j + 1]
lst1[j + 1] = tmp
count_swap += 1 ## 统计交换次数
print(lst1, count, count_swap)
[1, 9, 8, 5, 6, 7, 4, 3, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9] 36 25
上面例子中特殊的情况（默认已经排序好）
方法1（每一次都比较）
lst=[ [1,9,8,5,6,7,4,3,2], [1,2,3,4,5,6,7,8,9] ]
lst1=lst[1]
print(lst1)
count=0
count_swap=0
length=len(lst1)
for i in range(length):
for j in range(length-i-1):
count+=1
if lst1[j] > lst1[j+1]:
tmp=lst1[j]
lst1[j]=lst1[j+1]
lst1[j+1]=tmp
count_swap+=1
print(lst1,count,count_swap)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9] 36 0
代码优化
lst = [[1, 9, 8, 5, 6, 7, 4, 3, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1]]
lst1 = lst[1]
print(lst1)
count = 0
count_swap = 0
length = len(lst1)
for i in range(length):
flag = False
for j in range(length - i - 1):
count += 1
if lst1[j] > lst1[j + 1]:
tmp = lst1[j]
lst1[j] = lst1[j + 1]
lst1[j + 1] = tmp
count_swap += 1
flag = True
if not flag:
break
print(lst1, count, count_swap)
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1] 8 0
下一篇：（八）多线程之queue