冒泡法实战案例

　　　　　　　　　　　　　　　　冒泡法实战案例

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　作者：尹正杰

一.冒泡法概述

冒泡法
　　属于交换排序
　　两两比较大小，交换位置。如同水泡咕嘟咕嘟往上冒
　　结果分为升序和降序排列

升序
　　n个数从左至右，编号从0开始到n-1，索引0和1的值比较，如果索引0大，则交换两者位置，如果索引1大，则不交换。继续比较索引1和2的值，将大值放在右侧。直至n-2和n-1比较完，第一轮比较完成。第二轮从索引0比较到n-2，因为最右侧n-1位置上已经是最大值了。依次类推，每一轮都会减少最右侧的不参与比较，直至剩下最后2个数比较。

降序
　　和升序相反

二.冒泡法原理

初始值：[1 9 8 5 6 7 4 3 2]

第一趟：[1 8 9 5 6 7 4 3 2] [1 8 5 9 6 7 4 3 2] [1 8 5 6 9 7 4 3 2] [1 8 5 6 7 9 4 3 2] [1 8 5 6 7 4 9 3 2] [1 8 5 6 7 4 3 9 2] [1 8 5 6 7 4 3 2 9]

第二趟：[1 8 5 6 7 4 3 2 9] [1 5 8 6 7 4 3 2 9] [1 5 6 8 7 4 3 2 9] [1 5 6 7 8 4 3 2 9] [1 5 6 7 4 8 3 2 9] [1 5 6 7 4 3 8 2 9] [1 5 6 7 4 3 2 8 9]

第三趟：[1 5 6 7 4 3 2 8 9] [1 5 6 4 7 3 2 8 9] [1 5 6 4 3 7 2 8 9] [1 5 6 4 3 2 7 8 9]

第四趟：[1 5 6 4 3 2 7 8 9] [1 5 4 6 3 2 7 8 9] [1 5 4 3 6 2 7 8 9] [1 5 4 3 2 6 7 8 9]

第五趟：[1 5 4 3 2 6 7 8 9] [1 4 5 3 2 6 7 8 9] [1 4 3 5 2 6 7 8 9] [1 4 3 2 5 6 7 8 9]

第六趟：[1 4 3 2 5 6 7 8 9] [1 3 4 2 5 6 7 8 9] [1 3 2 4 5 6 7 8 9]

第七趟：[1 3 2 4 5 6 7 8 9] [1 2 3 4 5 6 7 8 9]

第八趟：[1 2 3 4 5 6 7 8 9]

三.使用Python代码实现冒泡法

1>.版本一

 1 #！/usr/bin/env python
 2 #_*_conding:utf-8_*_
 3 #@author :yinzhengjie
 4 #blog:http://www.cnblogs.com/yinzhengjie
 5 
 6 
 7 import random
 8 
 9 nums_list = [
10     [1,2,3,4,5,6,7,8,9],
11     [1,2,3,4,5,6,7,9,8]
12 ]
13 
14 nums = nums_list[0]
15 print("原列表顺序:{}".format(nums))
16 random.shuffle(nums)            #我们把一个有序的列表顺序给他打乱
17 print("shuffle后列表顺序:{}".format(nums))
18 
19 length = len(nums)
20 
21 count_swap = 0
22 
23 count = 0
24 
25 for i in range(length):
26     for j in range(length - i - 1):
27         count += 1
28         if nums[j] > nums[ j + 1]:
29             tmp = nums[j]
30             nums[j] = nums[j+1]
31             nums[j+1] = tmp
32             count_swap += 1
33 
34 print("排序后列表的顺序:{},交换的次数:{},循环的次数:{}".format(nums,count_swap,count))

原列表顺序:[1, 2, 3, 4, 5, 6, 7, 8, 9]
shuffle后列表顺序:[1, 2, 6, 4, 7, 3, 5, 9, 8]
排序后列表的顺序:[1, 2, 3, 4, 5, 6, 7, 8, 9],交换的次数:7,循环的次数:36

以上代码执行结果戳这里

2>.版本二【优化版】

 1 #！/usr/bin/env python
 2 #_*_conding:utf-8_*_
 3 #@author :yinzhengjie
 4 #blog:http://www.cnblogs.com/yinzhengjie
 5 
 6 
 7 numlist = [
 8     [1,9,8,5,6,7,4,3,2],
 9     [1,2,3,4,5,6,7,9,8],
10     [1,2,3,4,5,6,7,8,9]
11 ]
12 
13 nums = numlist[1]
14 print("原列表顺序:{}".format(nums))
15 
16 length = len(nums)              #计算出列表的长度，时间复杂度为O(1)
17 
18 count_swap = 0
19 
20 count = 0
21 
22 for i in range(length):
23    flag = False                 #定义一个标志位，假设没有发生交换。
24    for j in range(length - i -1):
25        count += 1
26        if nums[j] > nums[j+1]:  #交换很耗时，因此我们应该想办法减少交换的次数
27            tmp = nums[j]
28            nums[j] =nums[j+1]
29            nums[j+1] = tmp
30            flag = True          #有人换位置
31            count_swap += 1
32    if not flag:                 #本次循环没有交换位置，表示现有的数字是有序的，我们可以终止循环。这样理论上较少循环的次数也可以节省一定的排序时间！
33         break
34 
35 print("排序后列表的顺序:{},交换的次数:{},循环的次数:{}".format(nums,count_swap,count))

原列表顺序:[1, 2, 3, 4, 5, 6, 7, 9, 8]
排序后列表的顺序:[1, 2, 3, 4, 5, 6, 7, 8, 9],交换的次数:1,循环的次数:15

以上代码输出结果戳这里

3>.使用解构的方式修改冒泡法

#！/usr/bin/env python
#_*_conding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie


numlist = [
    [1,9,8,5,6,7,4,3,2],
    [1,2,3,4,5,6,7,9,8],
    [1,2,3,4,5,6,7,8,9]
]

nums = numlist[1]
print("原列表顺序:{}".format(nums))

length = len(nums)              #计算出列表的长度，时间复杂度为O(1)

count_swap = 0

count = 0

for i in range(length):
   flag = False                 #定义一个标志位，假设没有发生交换。
   for j in range(length - i -1):
       count += 1
       if nums[j] > nums[j+1]:  #交换很耗时，因此我们应该想办法减少交换的次数
           nums[j],nums[j+1] = nums[j+1],nums[j]
           flag = True          #有人换位置
           count_swap += 1
   if not flag:                 #本次循环没有交换位置，表示现有的数字是有序的，我们可以终止循环。这样理论上较少循环的次数也可以节省一定的排序时间！
        break

print("排序后列表的顺序:{},交换的次数:{},循环的次数:{}".format(nums,count_swap,count))



#以上代码输出结果如下:
原列表顺序:[1, 2, 3, 4, 5, 6, 7, 9, 8]
排序后列表的顺序:[1, 2, 3, 4, 5, 6, 7, 8, 9],交换的次数:1,循环的次数:15

四.冒泡法总结

　　冒泡法需要数据一轮轮比较

　　可以设定一个标记判断此轮是否发生数据交换，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序

　　最差的情况是，初始顺序与目标顺序完全相反，遍历次数1,...,n-1之和n(n-1)/2

　　最好的情况是，初始顺序和目标顺序完全相同，遍历次数n-1

　　时间复杂度O(n²)