python 排序算法——冒泡排序

# 数据结构与算法
# 排序算法：--冒泡排序
#冒泡排序是一种简单直接暴力的排序算法，为什么说它暴力？因为每一轮比较可能多个元素
#移动位置，而元素位置的互换是需要消耗资源的，所以这是一种偏慢的排序算法，仅适用于
#对于含有较少元素的数列进行排序。

#稳定性：我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置，所以相同
#元素的相对顺序不可能改变，所以它是稳定排序

#比较性：因为排序时元素之间需要比较，所以是比较排序

#时间复杂度：因为它需要双层循环n*(n-1))，所以平均时间复杂度为O(n^2)

#空间复杂度：只需要常数个辅助单元，所以空间复杂度为O(1)，我们把空间复杂度为O(1)
#的排序成为原地排序（in-place）

#记忆方法：想象成气泡，一层一层的往上变大


def Bubble_sort(alist):
	a = len(alist)
	for i in range(n-1):
		res = True
		for j in range(n-1-i):
			if alist[j] > alist[j+1]:
				alist[j], alist[j+1] = alist[j+1], alist[j]				
				res = False
		if res == True:
			return
				
def Bubble_sort_2(alist):
	for i in range(len(alist)-1,0,-1):
		for j in range(i):
			if alist[j] > alist[j+1]:
				alist[j], alist[j+1] = alist[j+1], alist[j]

lis = [3,2,5,7,2,8,44,75,3]
Bubble_sort(lis)
print(lis)