冒泡排序（英语：Bubble Sort，台湾另外一种译名为：泡沫排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
a=[12,25,5,13,21,37] length=len(a)=6 1、2步骤如下：(第1轮)
[12, 25, 5, 13, 21, 37]--a[0]=12与a[1]=25比较-->[12, 25, 5, 13, 21, 37]
[12, 25, 5, 13, 21, 37]--a[1]=25与a[2]= 5比较-->[12, 5, 25, 13, 21, 37]
[12, 5, 25, 13, 21, 37]--a[2]=25与a[3]=13比较-->[12, 5, 13, 25, 21, 37]
[12, 5, 13, 25, 21, 37]--a[3]=25与a[4]=21比较-->[12, 5, 13, 21, 25, 37]
[12, 5, 13, 21, 25, 37]--a[4]=25与a[5]=37比较-->[12, 5, 13, 21, 25, 37]
- 针对所有的元素重复以上的步骤，除了最后一个。
经过步骤1、2后，列表最大元素排序到最后，即a[5]=37，再对
1.(第2轮)前5个元素做1、2步骤
2.(第3轮)前4个元素做1、2步骤
3.(第4轮)前3个元素做1、2步骤
4.(第5轮)前2个元素做1、2步骤
结束
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
a=[12,25,5,13,21,37,.....] 列表a长度length=len(a)
1.循环比较length-1轮，range(length)，即[0,1,2,3,4,5,...,length-1]
2.第i轮比较length-i个元素，range(length-1-i)(-1减1是因为i从0开始)
Python代码
def bubble_sort(array):
length=len(array)
for i in range(length):
for j in range(length-1-i):
if array[j]>array[j+1]:
print('第%s轮 第%s次' %(i+1,j+1),end=':')
print(array,end='--->')
array[j],array[j+1]=array[j+1],array[j]
print(array)
else:
print('第%s轮 第%s次' %(i+1,j+1),end='')
print(array,end='--->')
print(array)
return array
if __name__ == '__main__':
array=[12,25,5,13,21,37]
print(array)
print(bubble_sort(array))
运行结果
[12, 25, 5, 13, 21, 37]
第1轮 第1次:[12, 25, 5, 13, 21, 37]--->[12, 25, 5, 13, 21, 37]
第1轮 第2次:[12, 25, 5, 13, 21, 37]--->[12, 5, 25, 13, 21, 37]
第1轮 第3次:[12, 5, 25, 13, 21, 37]--->[12, 5, 13, 25, 21, 37]
第1轮 第4次:[12, 5, 13, 25, 21, 37]--->[12, 5, 13, 21, 25, 37]
第1轮 第5次:[12, 5, 13, 21, 25, 37]--->[12, 5, 13, 21, 25, 37]
第2轮 第1次:[12, 5, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第3次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第4次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第1次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第3次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第4轮 第1次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第4轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第5轮 第1次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
[5, 12, 13, 21, 25, 37]
** 改进1 在某一轮全部没有交换的情况下便退出，排序完成 **
从以上结果可以看出：
1.在第2轮 第1次比较排序之后，列表便已经排序完成
2.后面几轮比较还是会进行，造成了资源浪费
3.改进思路：若某一轮没有一次比较排序的，即代表已经排序完成，下一轮不再比较，直接退出
4.程序中设置一个标志位变量flag，每次若有比较排序则置为True，若某一轮过后，flag还为false，则说明没有进行交换，排序已经完成
代码如下：
def bubble_sort(array):
length=len(array)
flag=1 #交换标志
for i in range(length):
if flag:
flag=0
for j in range(length-1-i):
if array[j]>array[j+1]:
print('第%s轮 第%s次' %(i+1,j+1),end=':')
print(array,end='--->')
array[j],array[j+1]=array[j+1],array[j]
flag=1
print(array)
else:
print('第%s轮 第%s次' %(i+1,j+1),end=':')
print(array,end='--->')
print(array)
else:
break
return array
if __name__ == '__main__':
array=[12,25,5,13,21,37]
print(array)
print(bubble_sort(array))
运行结果
[12, 25, 5, 13, 21, 37]
第1轮 第1次:[12, 25, 5, 13, 21, 37]--->[12, 25, 5, 13, 21, 37]
第1轮 第2次:[12, 25, 5, 13, 21, 37]--->[12, 5, 25, 13, 21, 37]
第1轮 第3次:[12, 5, 25, 13, 21, 37]--->[12, 5, 13, 25, 21, 37]
第1轮 第4次:[12, 5, 13, 25, 21, 37]--->[12, 5, 13, 21, 25, 37]
第1轮 第5次:[12, 5, 13, 21, 25, 37]--->[12, 5, 13, 21, 25, 37]
第2轮 第1次:[12, 5, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第3次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第4次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第1次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第3轮 第3次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
[5, 12, 13, 21, 25, 37]
** 改进2 局部冒泡排序 **
在每次两个数比较交换位置后，交换到前面的数再与它前面的数比较
def bubble_sort(array):
length=len(array)
flag=1 #交换标志
for i in range(length):
if flag:
flag=0
for j in range(length-1-i):
part=0
if array[j]>array[j+1]:
print('第%s轮 第%s次' %(i+1,j+1),end=':')
print(array,end='--->')
array[j],array[j+1]=array[j+1],array[j]
flag=1
part=1
print(array)
else:
print('第%s轮 第%s次' %(i+1,j+1),end=':')
print(array,end='--->')
print(array)
if part:
if j-1>=0:
if array[j-1]>array[j]:
array[j-1],array[j]=array[j],array[j-1]
else:
break
return array
if __name__ == '__main__':
array=[12,25,5,13,21,37]
print(array)
print(bubble_sort(array))
运行结果
[12, 25, 5, 13, 21, 37]
第1轮 第1次:[12, 25, 5, 13, 21, 37]--->[12, 25, 5, 13, 21, 37]
第1轮 第2次:[12, 25, 5, 13, 21, 37]--->[12, 5, 25, 13, 21, 37]
第1轮 第3次:[5, 12, 25, 13, 21, 37]--->[5, 12, 13, 25, 21, 37]
第1轮 第4次:[5, 12, 13, 25, 21, 37]--->[5, 12, 13, 21, 25, 37]
第1轮 第5次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第1次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第2次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第3次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
第2轮 第4次:[5, 12, 13, 21, 25, 37]--->[5, 12, 13, 21, 25, 37]
[5, 12, 13, 21, 25, 37]
