龙空技术网

python实现基本算法之冒泡排序(Bubble Sort)

写Python的小可爱 198

前言:

而今姐妹们对“python实现冒泡排序”可能比较注重,姐妹们都想要知道一些“python实现冒泡排序”的相关资讯。那么小编同时在网摘上网罗了一些关于“python实现冒泡排序””的相关内容,希望你们能喜欢,朋友们快快来学习一下吧!

评判一个算法的好坏的标准:时间复杂度、空间复杂度

冒泡算法是什么?

冒泡排序(Bubble Sort)是一种计算机科学领域较简单的排序算法;

原理:它重复的走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序是错误的就交换。一直重复的进行到没有相邻的元素交换为止。(一般情况进行N次即可,第N次一定会把第N小的元素放到正确的位置)

这个算法名字的由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端(升序或者降序),如同气泡浮到顶端一样。故名“冒泡排序”

算法过程图解

代码实现

"""Bubble Sort冒泡排序"""def bubble_sort(alist):    for i in range(len(alist)-1):        for j in range(1,len(alist)-i):            # 这里的j和j-1就是相邻的两个数,上面的i,这是一个计数的            if alist[j-1]>alist[j]:                alist[j-1],alist[j]=alist[j],alist[j-1]if __name__ == '__main__':    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]    print(f'原列表的顺序:{alist}')    bubble_sort(alist)    print(f'选择排序之后的列表的顺序:{alist}')

这一个代码写,执行的时候可能会有很多 的无效执行,所以,下面的可以改进一下!

这个方法就是一般情况,会执行N次!(一般情况进行N次即可,第N次一定会把第N小的元素放到正确的位置)

为什么上面的算法是多了几次无效的循环呢?!

看下面图片!

代码改进

代码改进"""Bubble Sort冒泡排序"""# 设置一个交换的flag,只要本次循环有交换,就会变化成True,# 如果没有的话,就是False,这样的话,如果最后都是顺序的,# 就可以少循环很多次def bubble_sort(alist):    for i in range(len(alist)-1):        # 设置是否交换的旗帜        flag = False        for j in range(1,len(alist)-i):            # 这里的j和j-1就是相邻的两个数,上面的i,这是一个计数的            if alist[j-1]>alist[j]:                alist[j-1],alist[j]=alist[j],alist[j-1]                # 发生交换了,设置为True                flag=True        if not flag:            breakif __name__ == '__main__':    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]    print(f'原列表的顺序:{alist}')    bubble_sort(alist)    print(f'选择排序之后的列表的顺序:{alist}')

这一个改进就是设置了一个flag,检测是否还有交换的元素,如果没有交换的元素,就代表整个列表已经是有序的啦!虽然没有循环完毕,依旧可以输出了。可以,代码运行时间就会缩短不少!

评判算法

时间复杂度:O(N^2)

空间复杂度:O(1)

算法稳定性:稳定的排序

最后多说一句,小编是一名python开发工程师,这里有我自己整理了一套最新的python系统学习教程,包括从基础的python脚本到web开发、爬虫、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编,并在后台私信小编:“01”即可领取。

标签: #python实现冒泡排序 #python冒泡排序详解