欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

冒泡排序(python实现)

程序员文章站 2022-03-24 15:44:50
...

``冒泡排序,简单的来说就是在一组无序的列表中,遍历整个列表,比较相邻的数,后一个比前一个大的话,两个数就调换位置,然后继续比较,一直比较到最大的那个数排到了最后面的位置,然后继续遍历数组,因为这次最后一个数已经排好了,所以只用遍历到倒数第二位就行了,这次比较完,就可以把第二大的数放到了倒数第二个位置,依此类推,直到整个列表成为有序(升序)列表即可退出循环。
python实现:

def bubble_sort(list):
		for i in range(n-1):   # 外循环控制遍历的次数
			for j in range(n-1-i):  # 内循环控制遍历到哪一位
				if list[j] > list[j+1]:
					list[j], list[j+1] = list[j+1],list[j]  # 如果后一个数比前一个数大,两个数就交换位置
		return list  # 在全部遍历完以后,返回排序好的列表

这时候无序的列表采用冒泡排序的时间复杂度是O(n^2),也就是最坏的时间复杂度,那么假如这个列表一开始就是有序的列表呢?
我们这时候可以优化一下上面的代码:

def bubble_sort(list):
		n = len(list)  
		for i in range(n-1):   # 外循环控制遍历的次数
				count = 0  # 定义一个变量,记录有没有发生交换位置
			for j in range(n-1-i):  # 内循环控制遍历到哪一位
				if list[j] > list[j+1]:
					list[j], list[j+1] = list[j+1],list[j]  # 如果后一个数比前一个数大,两个数就交换位置
					count += 1  # 如果有数字发生交换,那么就对count加一
			if count == 0:  # 假如遍历完一次,count还等于0,那么就代表这个列表已经是有序的了,所以我们把它直接return 就行了
					return list		
		return list  # 在全部遍历完以后,返回排序好的列表

优化过后的代码,就可以在列表是有序的情况下,只遍历一次就可以退出了,也就是最好时间复杂度为O(n)的情况。