一，什么是冒泡排序?
1，冒泡排序和快速排序都属于交换排序
所谓交换，就是对序列中两个元素根据键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点：将键值较大的元素向序列的尾部移动，键值较小的元素向序列的前部移动
2,冒泡排序:Bubble Sort，是一种最基础的交换排序,
冒泡排序：从序列的一端开始往另一端冒泡，依次比较相邻的两个数的大小，
按需要对数据进行交换，达到最终的排序效果
3，排序过程:以升序排序为例:
设数组长度为n
a, 每轮比较相邻的前后两个数据，如果前面数据大于后面的数据，就将二个数据交换。
b, 每轮都对未排序部分进行遍历，
最大的数据会被交换到未排序部分的最后,
下一轮循环时，对比较的数字范围-1，
不再比较已交换到最后的最大数字
二，示意图:
1，冒泡排序的过程
第一轮遍历前的数据:
比较3和5，无需交换
比较5和9，无需交换
比较9和7，需要交换：
比较9和2，需要交换
比较9和1，需要交换
第二轮遍历后的结果:(注意此轮不再比较最后的9,只比较前5个数字即可)
第三轮遍历后的结果:(注意此轮不再比较最后的7、9,只比较前4个数字即可)
第四轮遍历后的结果:
第五轮遍历后的结果:
最终结果:
2, 总结:
设数据长度为n
a，需要进行多少轮冒泡？
n-1轮，-1是因为剩下最后一个数字之后无需再排序
b，每轮要比较多少个数字？
设当前为第i轮(从0开始),需要比较n-i个数字
c, 每轮要比较多少次?
因为每次比较两个，到最后一个数字时无需再比较,所以需要比较n-i-1次
三，动画演示:
说明：刘宏缔的架构森林—专注it技术的博客，
网址：https://imgtouch.com
本文: https://blog.imgtouch.com/index.php/2024/04/12/python-suan-fa-pai-xu-mao-pao-pai-xu/
代码: https://github.com/liuhongdi/ 或 https://gitee.com/liuhongdi
说明：作者:刘宏缔 邮箱: [email protected]
四，演示代码:
代码:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# data:要排序的数据
def bubble(data):
n = len(data) # 得到数据长度n
# 排序，对数据遍历n-1轮,因为最后剩下一个元素时，无需再排
for i in range(n - 1):
end = n - i - 1 # 每轮需比较n-i个数据，共需比较n-i-1次
for j in range(0, end): # 开始比较相邻的两个数据
if (data[j] > data[j + 1]): # 前一个元素>后一个元素时，交换
data[j], data[j + 1] = data[j + 1], data[j]
print(f"第{i + 1}轮排序后:", data)
data = [3, 5, 9, 7, 2, 1]
print("排序开始前:", data)
bubble(data)
print("排序完成后:", data)
|
运行结果:
排序开始前: [3, 5, 9, 7, 2, 1]
第1轮排序后: [3, 5, 7, 2, 1, 9]
第2轮排序后: [3, 5, 2, 1, 7, 9]
第3轮排序后: [3, 2, 1, 5, 7, 9]
第4轮排序后: [2, 1, 3, 5, 7, 9]
第5轮排序后: [1, 2, 3, 5, 7, 9]
排序完成后: [1, 2, 3, 5, 7, 9]五，总结
冒泡排序：有两个嵌套的循环，用时间较长
平均时间复杂度: O(n²)
最差情形复杂度: O(n²)
空间复杂度: O(1)