算法009_冒泡排序
2024-01-08 本文已影响0人
为宇绸缪
冒泡排序（Bubble Sort）
- 列表每两个相邻的数，如果前面比后面大，则交换这两个数
- 一趟排序完成后，则无序区减少一个数，有序区增加一个数
- 代码关键点：趟、无序区范围
- 第 0 趟的时候无序区没有数
- 第 n - 1 趟的时候有一个数
- 第 i 趟的时候，无序的长度是 n - i - 1
- 最底下的是无序区，最上面的是有序区。无序区慢慢减少变的只剩一个，有序区慢慢增加到 n - 1
- 时间复杂度：
图解冒泡排序
箭头从数值 7 开始，第一趟比较 7 和 5，7 > 5 进行交换
接着 7 和 4 相比，7 > 4，继续交换
接着 7 和 6 相比，7 > 6，继续交换
冒泡排序交换过程01
接着 7 和 3 比，进行交换
接着 7 和 8 比，7 < 8，不交换数字，但是箭头一直得向上
接着 8 和 2 比，进行交换
冒泡排序交换过程02
接着 8 和 9 比，不交换，箭头上移
接着 9 和 1比，交换，此时最大的数 9 已经在最上面了
这就是冒泡排序的一趟。注意最后只会指到倒数第二个元素（从下往上的倒数第二个元素），因为它永远都要和它后面的数进行比较。
在这一趟的过程当中，有一个最大的数上去了
冒泡排序交换过程03
当一趟排序完成之后，箭头上面的就是有序区，箭头下面就是无序区
然后接着会对无序区进行排序
整个排序算法需要进行 n - 1 趟，因为最后剩下来的就是最小的或者最大的数
代码
import random
def bubble_sort(target_list):
for i in range(len(target_list) - 1): # 第i趟
for j in range(len(target_list) - i - 1): # 箭头指向
if target_list[j] > target_list[j + 1]:
# 箭头指的数大于箭头指的后一个数
target_list[j], target_list[j + 1] = target_list[j + 1], target_list[j]
test_list = [random.randint(0, 100) for i in range(10)]
print("排序之前: ", test_list)
bubble_sort(test_list)
print("排序之后: ", test_list)
"""
排序之前: [95, 20, 68, 74, 42, 85, 40, 81, 85, 92]
排序之后: [20, 40, 42, 68, 74, 81, 85, 85, 92, 95]
"""
改进版
冒泡排序改进：如果在排序的过程当中，没有发生任何数据的交换，就可以认为这个列表已经被排好序了，就可以不用排了
在排序之前添加标志位 exchange = False，如果发生了排序就设置 exchange = True。如果一趟排序结束之后，exchange 为 False，说明没有交互，就可以直接跳出循环，结束排序
def bubble_sort(target_list):
for i in range(len(target_list) - 1): # 第i趟
exchange = False
for j in range(len(target_list) - i - 1): # 箭头指向
if target_list[j] > target_list[j + 1]:
# 箭头指的数大于箭头指的后一个数
target_list[j], target_list[j + 1] = target_list[j + 1], target_list[j]
exchange = True
if exchange is False:
return
print("交换之后的数组: ", target_list)
test_list = [9, 1, 2, 3, 4, 5, 6, 7, 8]
print("原始数组: ", test_list)
bubble_sort(test_list)
"""
原始数组: [9, 1, 2, 3, 4, 5, 6, 7, 8]
交换之后的数组: [1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
如果传入的数据是已经按照要求排好的，进阶版本就只需要排一趟，基础版本需要 n - 1 趟
