概念
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复的遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作室重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（越大）的元素会慢慢“浮到”数列的顶端。
运作过程
- 比较相邻的元素，如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完之后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法分析
时间复杂度：
- 最优时间复杂度：O（n） 表示遍历一次发现没有任何可以交换的元素，排序结束。）
- 最坏时间复杂度：O（n^2）每一个都要交换。
- 稳定性：稳定
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
| def bubble_sort_1(alist):
"""
两个for循环嵌套
以 alist = [1,3,2,5,7,6,4]为例
第一次需要遍历到索引6，第二次5，直到索引0
:param alist:
:return:alist:list
"""
for k in range(0,len(alist)-1):
for i in range(0,len(alist)-1-k):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
return alist
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def bubble_sort_2(alist):
"""
while循环+for循环嵌套
以 alist = [1,3,2,5,7,6,4]为例
主要是k的值的变化
:param alist:
:return:alist:list
"""
k = 0
while k != len(alist)-1:
k += 1
for i in range(0,len(alist)-k):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
return alist
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| def bubble_sort_3(alist):
"""
while循环+for循环嵌套
以 alist = [1,3,2,5,7,6,4]为例
如果遍历的时候没有发现要交换的，则这个列表已经是一个排好序的，则直接break
:param alist:
:return:alist:list
"""
for k in range(0,len(alist)-1):
count = 0
for i in range(0,len(alist)-1-k):
if alist[i] > alist[i+1]:
count += 1
alist[i],alist[i+1] = alist[i+1],alist[i]
if count == 0:
break
return alist
|
在这个优化里面只有当遍历完之后发现所有的都不需要操作的时候才会break，所以它的最乐观的时间复杂度还是O（n）,最差的时间复杂度还是O（n^2)，只在特定的情况下才会有优化的效果。我也尝试着用time模块的time.time()函数来获取程序运行的时间 ，但是程序运行的时间太短了，最终都显示0.0，我也懒得去增大列表的长度了（狗头）。
