利用python实现冒泡排序法
冒泡排序法：
- 属于交换排序
- 两两比较大小，交换位置。如同水泡咕嘟咕嘟往上冒
- 结果分为升序和降序排列
升序排序原理：
- n个数从左至右，索引编号从0开始到n-1，索引0和1的值比较，如果索引0大，则交换两者位置，如果索引1大，则不交换。继续比较索引1和2的值，将大值放在右侧，直到索引n-2和n-1比较完，第一轮比较完成，此时，位于最右侧的值为最大的数。
- 第二轮从索引0开始比较到索引n-2，因为最右侧n-1位置上已经是最大值了。依次类推，每一轮都会减少最右侧的不参与比较，直至剩下的最后2个数比较。（降序和升序相反）
冒泡排序算法代码：
#冒泡排序法
import time
data=[1,2,7,4,5,6]
count=0 #记录比较次数
count_swap=0 #记录交换次数
print("待排序的列表：",data)
start_time=time.time()
for i in range(len(data)):
for j in range(len(data)-i-1):
count+=1
if data[j]>data[j+1]:
tmp=data[j]
data[j]=data[j+1]
data[j+1]=tmp
count_swap+=1
print("第{0}轮:索引{1}和索引{2}比较后的结果：{3}".format(i+1,j,j+1,data))
span_time=(time.time()-start_time)*1000
print("排序结果为：{0}，总比较次数为：{1}，交换次数为：{2}，耗时：{3} 毫秒".format(data,count,count_swap,span_time))运行结果如下：
由运行结果可以看出，经过第1轮的循环比较后，列表已经达到了从小到大的排序结果，第2轮循环过程中，没有出现元素位置交换，第3/4/5轮的循环比较并没有比较的必要。由此可以对算法进行优化，当某轮循环后没有元素进行位置交换，则说明达到了排序结果，跳出循环，程序终止。
算法优化代码：
#冒泡排序法优化算法
import time
data=[1,2,7,4,5,6]
count=0 #记录比较次数
count_swap=0 #记录交换次数
print("待排序的列表：",data)
start_time=time.time()
for i in range(len(data)):
flag=False #定义一个标记，初始值为False，当某轮循环中存在元素位置交换，则为True
for j in range(len(data)-i-1):
count+=1
if data[j]>data[j+1]:
tmp=data[j]
data[j]=data[j+1]
data[j+1]=tmp
count_swap+=1
flag=True
print("第{0}轮:索引{1}和索引{2}比较后的结果：{3}".format(i+1,j,j+1,data))
if not flag:
break
span_time=(time.time()-start_time)*1000
print("排序结果为：{0}，总比较次数为：{1}，交换次数为：{2}，耗时：{3}毫秒".format(data,count,count_swap,span_time)运行结果如下：
由上述运行结果可以看出，程序进行了2轮循环比较后可以确认达到了最终排序结果，没有进行后面3轮的比较，由此也节省了算法运行时间，提升算法效率。
算法总结：
- 冒泡法需要数据一轮轮进行比较
- 可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序
- 最差的排序情况是：初始顺序与目标顺序完全相反，遍历次数为1,2....n-1之和n(n-1)/2
- 最好的排序情况是：初始顺序与目标顺序完全相同，遍历次数为n-1
- 时间复杂度O(n**2)