基金会网站开发方案/平台推广文案

冒泡排序法

冒泡排序又称为交换排序法，是从观察水中气泡变化构思而成的，原理是从第一个元素开始，比较相邻元素的大小，若大小有误，则对调后再进行下一个元素的比较，就仿佛气泡逐渐从水底升到水面上一样。如此扫描完一次之后，就可以确保最后一个元素位于正确的顺序。接着逐步进行第二次扫描，直到完成所有元素的排序关系为止

冒泡分析法：

• 最后的情况个平均情况均需比较(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2次；事件复杂度为O(n^2)，最好的情况只需完成一次扫描，发现没有执行数据的交换操作，就表示已经排序完成，所以只做了n-1次比较，时间复杂度为O(n)
• 由于冒泡排序是相邻两个数据相互比较和对调，并不会更改其原本排列的顺序， 因此时稳定排序法
• 只需一个额外的空间，所以空间复杂度为最佳
• 此排序法适用于数量小或有部分数据已经排序的情况

例子：设计一个程序，使用冒泡排序

data = [3,2,7,4,1,5,6,8]
print('原始数据是：')
for i in range (8):print('[%2d]'%data[i],end='')
print()
for i in range(8):for j in range(8 - 1):if data[j] > data[j+1]:temp = data[j]data[j] = data[j+1]data[j+1] = tempprint('第%2d排序之后：' %(i+1),end='')for k in range(8):print('[%2d]'%data[k],end='')print()
print("排序的结果是：")
for i in range(8):print('[%2d]'%data[i],end='')

优化的冒泡排序

冒泡排序有一个缺点，就是无论数据是否已经排序完成，都固定会执行n(n-1)/2次，我们可以使用哨岗的形式，如果排序结束，就终止程序，又可以得到正确的排序结果，以此来提高程序执行的效率。就是在每次进入外层循环时声明一个变量，就是哨岗，如果进入了内部循环说明排序没有结束，就可以继续程序，如果没有进入内部循环，就说明排序已经完成，就结束循环

def showData(data): #循环打印数据for i in range(6):print('%3d'%data[i],end='')print()def bubble(data):for i in range(5,-1,-1):flag = 0    #flag用来判断是否执行了交换for j in range(i):if data[j] > data[j + 1]:data[j],data[j + 1] = data[j + 1],data[j]flag += 1   #如果发生了交换，flag就不是0if flag == 0:breakprint('第%d次排序:'%(6-i),end='')for j in range(6):print('%3d'%data[j],end='')print()print('排序之后的结果：',end='')showData(data)def main():data=[4,6,2,7,8,9]  #原始数据print('改进的冒泡排序测试用的原始数据：')bubble(data)if __name__ == '__main__':main()