冒泡排序(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)的情况。
上一篇: 冒泡排序(Python实现)
下一篇: 快速乘法、快速幂 算法