冒泡排序 -- 稳定算法

基本原理

1, 相邻的元素比较,如果前一个元素大于后一个元素,则交换位置.
2, 一次遍历后,最大的元素会跑到最后.
3, 第二次遍历就只需要比较前len(arr) - i - 1个元素了,因为后面的元素肯定都 比前面的元素要大了.
4, 时间复杂度为O(n^2), 空间复杂度为O(1)因为并没有创建新的数组. 是个稳定的算法.

举例

对一个列表进行冒泡排序【升序】
[12,2,34,23,45,13]
1轮: 5 / 比较次数
[2,12,23,34,13,45] 最大45
2轮： 4次
[2,12,23,13,34] 第二大 34
3轮： 3次
[2,12,13,23] 第三大 23
4轮： 2次
[2,12,13] 第四大13
5轮： 1次
[2,12] 第五大12
循环：比较轮数 = 元素个数-1
每轮比较的次数 = 元素的个数-比较的轮数

code

lst = [12,2,34,23,45,13]
for i in range(1,len(lst)): # 外循环, 比较轮数
	for j in range(len(lst)-i): # 内循环, 每轮比较的次数
		if lst[j] > lst[j+1]: # 如果前一位数比第二位数大
			lst[j], lst[j+1] = lst[j+1], lst[j] # 则对换位置

封装

def bubble_sort(arr, revers=False):
	'''
	revers, 默认为升序
	revers = True, 降序排列
	'''
	length = len(arr)
	for i in range(length-1):
		swapped = False # 一次循环之后, 如没有进行一次交换, 说明arr本身就有序, 则无需继续执行代码, 直接退出
		for j in range(length-1-i):
			if arr[j] > arr[j+1]:
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = True
		if not swapped:break
	if revers == True:
		arr.reverse()
	return arr