python冒泡排序

冒泡排序

冒泡排序：重复遍历需要排序的数列，一次比较俩个元素，如果他们的顺序错误就把他们交换过来，遍历数列的工作是重复的进行指导没有再需要交换，完成排序。
算法过程如下：

• 比较相邻元素，如果第一个比第二个大（升序），交换二者的位置。
• 对每一对相邻元素做同样的工作，从第一队到结尾的最后一对。最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤（最后一个为最大值，不需要）
• 持续每次对越来越少的元素重复以上步骤，直到没有任何一对数字需要比较。

分析

对一个序列需要进行n-1一次冒泡过程，每次对应的比较次数从第一次的（n-1）次逐步减少为1。
代码实现：
def maopao_sort(alist):
count=0
for j in range(len(alist)-1,0,-1):
“”“”表示从第一个数到n-1个数每次冒泡需要比较的次数”“”
for i in range(j):
if alist[i]>alist[i+1]:
alist[i] , alist[i + 1] = alist[i+1],alist[i]
count+=0 ##改进
if count==0: ##改进
return ##改进
li = [54,26,93,17,77,31,44,55,20]
maopao_sort(li)
print(li)

时间复杂度

• 最优复杂度O(n)
• 最坏复杂度O(n^2)

• 稳定性：稳定

  代码改进：如果序列初始便有序，则直接退出即可。