python实现·十大排序算法之冒泡排序(Bubble Sort)
本帖最后由 lb971216008 于 2020-7-10 16:51 编辑有没有python学习的微信群，加我一个呗,我的vx：blingtu2020，加我备注拉我入群
python实现·十大排序算法之冒泡排序(Bubble Sort)简介冒泡排序(Bubble Sort)是经典排序算法之一，属于交换排序的一种，基本的排序思路是：从头开始两两元素进行比较，大的元素就往上冒，这样遍历一轮后，最大的元素就会直接筛选出来。然后再重复上述操作，即可完成第二大元素的冒泡。以此类推，直到所有的元素排序完成。算法实现步骤
[*]比较相邻的元素，如果第一个比第二个大，就交换它们两个(确定排序规则：从小到大或从大到小)；
[*]对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对；
[*]针对所有的元素重复以上的步骤，除了最后一个；
[*]重复步骤1~3，直到没有任何一对元素需要比较，那么排序完成。
Python 代码实现 # bubble_sort 代码实现
from typing import List
# 冒泡排序
def bubble_sort(arr: List):
"""
冒泡排序(Bubble sort)
:param arr: 待排序的List,此处限制了排序类型为int
:return: 冒泡排序是就地排序(in-place)
"""
length = len(arr)
if length <= 1:
return
for i in range(length):
is_made_swap = False## 设置标志位，若本身已经有序，则直接break
for j in range(length - i - 1):
if arr > arr:
arr, arr = arr, arr
is_made_swap = True
if not is_made_swap:
break # 测试数据
if __name__ == '__main__':
import random
random.seed(54)
arr =
print("原始数据：", arr)
bubble_sort(arr)
print("冒泡排序结果：", arr) # 输出结果
原始数据：
冒泡排序结果： 动画演示https://pic3.zhimg.com/v2-2e6482e632145bbd1962223d343ed68e_b.webp算法分析
[*]时间复杂度如果数据一开始就是顺序，那么只需1趟排序即可完成。所需的比较次数C和记录移动次数M均达到最小值，即：
所以，冒泡排序最好的时间复杂度为O(n)。如果数据一开始是逆序的，则需要进行n-1趟排序，每趟要进行n-i次比较，且每次比较必须移动记录3次来达到交换记录位置。此时，比较和移动次数均达到最大值：
[*]空间复杂度空间复杂度就是在交换元素时那个临时变量所占的内存空间。最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为0；最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n);平均的空间复杂度为：O(1);
[*]稳定性由于在比较过程中，当两个相同大小的元素相邻，只比较大或者小，但不会交换位置。而当两个相等元素距离较远时，也只会把它们交换到相邻的位置。也就是说排序过程中，相等元素的位置前后关系不会发生任何变化，所以算法是稳定的。
[*]综合评价
时间复杂度(平均)时间复杂度(最好)时间复杂度(最坏)空间复杂度排序方式稳定性
in-place稳定
联系我们个人博客网站：http://www.bling2.cn/Github地址：https://github.com/lb971216008/Use-Python-to-Achieve知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve博客园：https://www.cnblogs.com/Use-Python-to-Achievehttps://img-blog.csdnimg.cn/2020051711241059.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xiOTcxMjE2MDA4,size_16,color_FFFFFF,t_70#pic_center
一个鱼币，一次一个，每人限三次，神奇。 永恒的蓝色梦想 发表于 2020-5-20 21:04
一个鱼币，一次一个，每人限三次，神奇。
鱼C论坛怎么用Markdown，求助，弄过来全是乱码 lb971216008 发表于 2020-5-20 21:09
鱼C论坛怎么用Markdown，求助，弄过来全是乱码
Markdown 还在测试，没有开放 永恒的蓝色梦想 发表于 2020-5-20 21:11
Markdown 还在测试，没有开放
你是谁？机器人还是管理员？认识风介吗，我是来打广告的 lb971216008 发表于 2020-5-20 21:18
你是谁？机器人还是管理员？认识风介吗，我是来打广告的
我是人。
风介？大概是之前的版主吧，不认识。
你告诉我你是打广告的，是想让我？ 很喜欢这个代码，继续补充算法的知识 鱼币 WOW。我要鱼币 {:10_297:}
页:
[1]