冒泡排序（Python实现）

2024-10-12 02:12:56

目录

1. while版本--冒泡排序
2. for版本--冒泡排序
3. 测试用例
4. 算法时间复杂度分析

1. while版本--冒泡排序

def bubble_sort_while(a_list):

	"""冒泡排序 while版本"""

	num = len(a_list)

	j = 0

	while j < num-1:

		i = 0

		count = 0;

		while i < num-1-j:

			if a_list[i] > a_list[i+1]:

				a_list[i],a_list[i+1] = a_list[i+1], a_list[i]

				count += 1

			i += 1

		# 优化冒泡排序，对于有序列表

		if count == 0:

			break

		j += 1

	return a_list

2. for版本--冒泡排序

def bubble_sort_for(b_list):

	"""冒泡排序 for版本"""

	num = len(b_list)

	for j in range(0, num-1):

		count = 0

		for i in range(0, num-1-j):

			if b_list[i] > b_list[i+1]:

				b_list[i],b_list[i+1] = b_list[i+1], b_list[i]

				count += 1

		# 优化冒泡排序，对于有序列表

		if count == 0:

			break

	return b_list

3. 测试用例

if __name__ == '__main__':

	a_list = [2,1,4,8,9,6]

	print(bubble_sort_while(a_list))

	b_list = [8,1,5,9,10,20]

	print(bubble_sort_for(b_list))

4. 算法时间复杂度分析

最好时间复杂度：O(n)

最坏时间复杂度：O(n²)

稳定性：稳定

最新文章

热门文章