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

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

基本算法—01、冒泡排序(Bubble Sort)算法
后面几天会把选择排序，插入排序，归并排序，快速排序等等都发布的！欢迎大家批评指正！

文章目录

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

0、前言
1、冒泡算法是什么？
2、算法过程图解
3.1、代码实现
3.2、代码改进
4、评判算法

0、前言

评判一个算法的好坏的标准：

时间复杂度
空间复杂度

1、冒泡算法是什么？

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

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

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

2、算法过程图解

3.1、代码实现

代码如下（示例01）：

"""
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小的元素放到正确的位置）

为啥上面的算法是多了几次无效的循环呢？！
看下面图片！

3.2、代码改进

代码如下（示例02）：

"""
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: break if __name__ == '__main__': alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(f'原列表的顺序：{alist}') bubble_sort(alist) print(f'选择排序之后的列表的顺序：{alist}')