利用python实现冒泡排序法_python 冒泡排序法

冒泡排序法：

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

升序排序原理：

1. n个数从左至右，索引编号从0开始到n-1，索引0和1的值比较，如果索引0大，则交换两者位置，如果索引1大，则不交换。继续比较索引1和2的值，将大值放在右侧，直到索引n-2和n-1比较完，第一轮比较完成，此时，位于最右侧的值为最大的数。
2. 第二轮从索引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. 可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序
3. 最差的排序情况是：初始顺序与目标顺序完全相反，遍历次数为1,2....n-1之和n(n-1)/2
4. 最好的排序情况是：初始顺序与目标顺序完全相同，遍历次数为n-1
5. 时间复杂度O(n**2)