python实现·十大排序算法之冒泡排序(Bubble Sort)

发布于: 2020 年 05 月 21 日
python实现·十大排序算法之冒泡排序(Bubble Sort)

简介

冒泡排序(Bubble Sort)是经典排序算法之一,属于交换排序的一种,基本的排序思路是:从头开始两两元素进行比较,大的元素就往上冒,这样遍历一轮后,最大的元素就会直接筛选出来。然后再重复上述操作,即可完成第二大元素的冒泡。以此类推,直到所有的元素排序完成。

算法实现步骤

  1. 比较相邻的元素,如果第一个比第二个大,就交换它们两个(确定排序规则:从小到大或从大到小);

  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对;

  3. 针对所有的元素重复以上的步骤,除了最后一个;

  4. 重复步骤1~3,直到没有任何一对元素需要比较,那么排序完成。

Python 代码实现

# bubble_sort 代码实现
from typing import List
# 冒泡排序
def bubble_sort(arr: List[int]):
"""
冒泡排序(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[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
is_made_swap = True
if not is_made_swap:
break

# 测试数据
if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("原始数据:", arr)
bubble_sort(arr)
print("冒泡排序结果:", arr)

# 输出结果
原始数据: [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
冒泡排序结果: [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

动画演示

冒泡排序动画演示

算法分析

  • 时间复杂度

如果数据一开始就是顺序,那么只需1趟排序即可完成。所需的比较次数C和记录移动次数M均达到最小值,即:

所以,冒泡排序最好的时间复杂度为O(n)

如果数据一开始是逆序的,则需要进行n-1趟排序,每趟要进行n-i次比较,且每次比较必须移动记录3次来达到交换记录位置。此时,比较和移动次数均达到最大值:

  • 空间复杂度

空间复杂度就是在交换元素时那个临时变量所占的内存空间。最优的空间复杂度就是开始元素顺序已经排好了,则空间复杂度为0;最差的空间复杂度就是开始元素逆序排序了,则空间复杂度为:O(n)​;

所以,平均的空间复杂度为:​O(1)​

  • 稳定性

由于在比较过程中,当两个相同大小的元素相邻,只比较大或者小,但不会交换位置。而当两个相等元素距离较远时,也只会把它们交换到相邻的位置。也就是说排序过程中,相等元素的位置前后关系不会发生任何变化,所以算法是稳定的。

  • 综合评价

联系我们

个人博客网站: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-Achieve

发布于: 2020 年 05 月 21 日 阅读数: 20
用户头像

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

评论

发布
暂无评论
python实现·十大排序算法之冒泡排序(Bubble Sort)