顺序表的冒泡排序 --python描述

最坏情况：顺序表数据无序

def bubble_sort(alist):
	'''顺序表的冒泡排序'''
	#游标只需要遍历到最后一个元素的前一位，就能比较完，所以每次遍历需要比较的次数为：len(alist)-1~1次
	for j in range(len(alist)-1,0,-1):
		#游标每次遍历的长度为j
		for i in range(j):
			if alist[i] > alist[i+1]:
				alist[i],alist[i+1]  = alist[i+1],alist[i]

li = [54,26,93,17,77,31,44]
bubble_sort(li)
print(li)

此时为最坏时间复杂度：n*n：O(n^2)

最优情况 顺序表有序

def bubble_sort(alist):
	for j in range(len(alist)-1,0,-1):
		count = 0
		for i in range(j):
			#若顺序表完全有序：e.g. [1,2,3,4,5,6],只需要从头到尾遍历一遍，确认是有序的就可以退出
			if alist[i] > alist[i+1]:
				alist[i],alist[i+1] = alist[i+1],alist[i]
				count += 1
		#遍历了一次，发现if没成立过,说明顺序表有序，直接退出函数
		if count == 0:
			return

此时就走了内层循环一次
最优时间复杂度为：O(n)

稳定性： 不稳定