冒泡排序
1. 功能实现
"""
冒泡排序
概述:
是一种交换排序, 相邻两个数比较, 如果前面的数比后面的数大, 就交换位置(由小到大排序时)
简介:
在冒泡排序过程中, 每一轮比较出一个最大的数放在队列的最后, 若使用m表示元素的总数, 那么每次冒泡排序需要执行 m-1 轮; n表示已经进行过的轮数, 则每轮需要比较 m-n-1 次, 所以冒泡排序的平均时间复杂度和最坏时间复杂度都是O(n²)
优点:
稳定, 空间复杂度低, 简单易懂
"""
def bubbleSort(num_list):
# 外层for循环控制要比较的轮数, 共需要执行 "长度-1" 次
for i in range(len(num_list) - 1):
# 内层for循环控制每一轮要比较的次数, 共需要执行 "长度-已执行的轮数-1" 次
for j in range(len(num_list) - i - 1):
print(f'第 {i + 1} 轮 第 {j + 1} 次 比较', end='\t')
# 如果前面的数比后面的数大, 就交换位置
if num_list[j] > num_list[j + 1]:
print(f'{num_list[j]} 和 {num_list[j + 1]} 交换位置', end='')
num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]
else:
print(f'{num_list[j]} 和 {num_list[j + 1]} 不交换位置', end='')
print(num_list)
print(f'第 {i + 1} 轮排序结果: {num_list}')
if __name__ == '__main__':
num_list = [7, 6, 3, 9, 1, 8]
print(f'排序前的数组顺序: {num_list}')
bubbleSort(num_list)
print(f'排序后的数组顺序: {num_list}')
控制台输出
排序前的数组顺序: [7, 6, 3, 9, 1, 8]
第 1 轮 第 1 次 比较 7 和 6 交换位置[6, 7, 3, 9, 1, 8]
第 1 轮 第 2 次 比较 7 和 3 交换位置[6, 3, 7, 9, 1, 8]
第 1 轮 第 3 次 比较 7 和 9 不交换位置[6, 3, 7, 9, 1, 8]
第 1 轮 第 4 次 比较 9 和 1 交换位置[6, 3, 7, 1, 9, 8]
第 1 轮 第 5 次 比较 9 和 8 交换位置[6, 3, 7, 1, 8, 9]
第 1 轮排序结果: [6, 3, 7, 1, 8, 9]
第 2 轮 第 1 次 比较 6 和 3 交换位置[3, 6, 7, 1, 8, 9]
第 2 轮 第 2 次 比较 6 和 7 不交换位置[3, 6, 7, 1, 8, 9]
第 2 轮 第 3 次 比较 7 和 1 交换位置[3, 6, 1, 7, 8, 9]
第 2 轮 第 4 次 比较 7 和 8 不交换位置[3, 6, 1, 7, 8, 9]
第 2 轮排序结果: [3, 6, 1, 7, 8, 9]
第 3 轮 第 1 次 比较 3 和 6 不交换位置[3, 6, 1, 7, 8, 9]
第 3 轮 第 2 次 比较 6 和 1 交换位置[3, 1, 6, 7, 8, 9]
第 3 轮 第 3 次 比较 6 和 7 不交换位置[3, 1, 6, 7, 8, 9]
第 3 轮排序结果: [3, 1, 6, 7, 8, 9]
第 4 轮 第 1 次 比较 3 和 1 交换位置[1, 3, 6, 7, 8, 9]
第 4 轮 第 2 次 比较 3 和 6 不交换位置[1, 3, 6, 7, 8, 9]
第 4 轮排序结果: [1, 3, 6, 7, 8, 9]
第 5 轮 第 1 次 比较 1 和 3 不交换位置[1, 3, 6, 7, 8, 9]
第 5 轮排序结果: [1, 3, 6, 7, 8, 9]
排序后的数组顺序: [1, 3, 6, 7, 8, 9]
1.1 发现问题
"""
发现问题:
当传入该序列时, 传入的序列在第一轮比较后, 排序就已经完成, 但是由于冒泡排序的总轮数未结束, 所以会继续比较下去, 浪费了资源
解决问题:
可以在每一轮比较开始前设置一个标记, 如果交换位置则改变标记值, 每轮比较结束后判断标记是否被改变: 如果没有改变说明本轮比较未发生位置交换, 则排序结束
"""
if __name__ == '__main__':
num_list = [6, 1, 2, 3, 4, 5]
print(f'排序前的数组顺序: {num_list}')
bubbleSort(num_list)
print(f'排序后的数组顺序: {num_list}')
控制台输出
排序前的数组顺序: [6, 1, 2, 3, 4, 5]
第 1 轮 第 1 次 比较 6 和 1 交换位置[1, 6, 2, 3, 4, 5]
第 1 轮 第 2 次 比较 6 和 2 交换位置[1, 2, 6, 3, 4, 5]
第 1 轮 第 3 次 比较 6 和 3 交换位置[1, 2, 3, 6, 4, 5]
第 1 轮 第 4 次 比较 6 和 4 交换位置[1, 2, 3, 4, 6, 5]
第 1 轮 第 5 次 比较 6 和 5 交换位置[1, 2, 3, 4, 5, 6]
第 1 轮排序结果: [1, 2, 3, 4, 5, 6]
第 2 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 2 次 比较 2 和 3 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 4 次 比较 4 和 5 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮排序结果: [1, 2, 3, 4, 5, 6]
第 3 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 3 轮 第 2 次 比较 2 和 3 不交换位置[1, 2, 3, 4, 5, 6]
第 3 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 3 轮排序结果: [1, 2, 3, 4, 5, 6]
第 4 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 4 轮 第 2 次 比较 2 和 3 不交换位置[1, 2, 3, 4, 5, 6]
第 4 轮排序结果: [1, 2, 3, 4, 5, 6]
第 5 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 5 轮排序结果: [1, 2, 3, 4, 5, 6]
排序后的数组顺序: [1, 2, 3, 4, 5, 6]
2. 算法优化 1
def bubbleSortOptimize1(num_list):
# 外层for循环控制要比较的轮数, 共需要执行 "长度-1"
for i in range(len(num_list) - 1):
# 设置标记
sorted = True
# 内层for循环控制每一轮要比较的次数, 共需要执行 "长度-已执行的轮数-1" 次
for j in range(len(num_list) - i - 1):
print(f'第 {i + 1} 轮 第 {j + 1} 次 比较', end='\t')
# 如果前面的数比后面的数大, 就交换位置
if num_list[j] > num_list[j + 1]:
print(f'{num_list[j]} 和 {num_list[j + 1]} 交换位置', end='')
num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]
# 发生位置交换, 说明排序未结束
sorted = False
else:
print(f'{num_list[j]} 和 {num_list[j + 1]} 不交换位置', end='')
print(num_list)
print(f'第 {i + 1} 轮排序结果: {num_list}')
# 本轮位置未发生交换, 说明排序完成, 结束循环
if sorted:
return
if __name__ == '__main__':
num_list = [6, 1, 2, 3, 4, 5]
print(f'排序前的数组顺序: {num_list}')
bubbleSortOptimize1(num_list)
print(f'排序后的数组顺序: {num_list}')
控制台输出
排序前的数组顺序: [6, 1, 2, 3, 4, 5]
第 1 轮 第 1 次 比较 6 和 1 交换位置[1, 6, 2, 3, 4, 5]
第 1 轮 第 2 次 比较 6 和 2 交换位置[1, 2, 6, 3, 4, 5]
第 1 轮 第 3 次 比较 6 和 3 交换位置[1, 2, 3, 6, 4, 5]
第 1 轮 第 4 次 比较 6 和 4 交换位置[1, 2, 3, 4, 6, 5]
第 1 轮 第 5 次 比较 6 和 5 交换位置[1, 2, 3, 4, 5, 6]
第 1 轮排序结果: [1, 2, 3, 4, 5, 6]
第 2 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 2 次 比较 2 和 3 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 4 次 比较 4 和 5 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮排序结果: [1, 2, 3, 4, 5, 6]
排序后的数组顺序: [1, 2, 3, 4, 5, 6]
2.1 发现问题
"""
发现问题:
通过分析执行结果, 在执行第一轮比较时, 从第三次比较开始便未发生任何位置交换, 说明后面的顺序已经排好了, 但是在第二轮比较时, 依然进行了后面的比较
解决问题:
记录下最后一次发生位置交换的位置, 作为下一轮比较的最后位置
"""
if __name__ == '__main__':
num_list = [1, 3, 2, 4, 5, 6]
print(f'排序前的数组顺序: {num_list}')
bubbleSortOptimize1(num_list)
print(f'排序后的数组顺序: {num_list}')
控制台输出
排序前的数组顺序: [1, 3, 2, 4, 5, 6]
第 1 轮 第 1 次 比较 1 和 3 不交换位置[1, 3, 2, 4, 5, 6]
第 1 轮 第 2 次 比较 3 和 2 交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 4 次 比较 4 和 5 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 5 次 比较 5 和 6 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮排序结果: [1, 2, 3, 4, 5, 6]
第 2 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 2 次 比较 2 和 3 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮 第 4 次 比较 4 和 5 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮排序结果: [1, 2, 3, 4, 5, 6]
排序后的数组顺序: [1, 2, 3, 4, 5, 6]
3. 算法优化 2
"""
进行两次冒泡排序优化:
第一次 优化比较的轮数, 即减少外层for循环执行次数
第二次 优化某一轮比较的次数, 即减少了内层for循环执行的次数
"""
def bubbleSortOptimize2(num_list):
inner = range(len(num_list) - 1)
# 外层for循环控制要比较的轮数, 共需要执行 "长度-1"
for i in range(len(num_list) - 1):
# 设置标记
sorted = True
# 内层for循环控制每一轮要比较的次数
for j in inner:
print(f'第 {i + 1} 轮 第 {j + 1} 次 比较', end='\t')
# 如果前面的数比后面的数大, 就交换位置
if num_list[j] > num_list[j + 1]:
print(f'{num_list[j]} 和 {num_list[j + 1]} 交换位置', end='')
num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]
# 发生位置交换, 说明排序未结束
sorted = False
# 记录一下最后交换的位置
last_change = j
else:
print(f'{num_list[j]} 和 {num_list[j + 1]} 不交换位置', end='')
print(num_list)
print(f'第 {i + 1} 轮排序结果: {num_list}')
# 本轮位置未发生交换, 说明排序完成, 结束循环
if sorted:
return
print(f'最后交换的位置: {last_change}')
# 改变下一轮比较的范围
inner = range(last_change)
if __name__ == '__main__':
num_list = [1, 3, 2, 4, 5, 6]
print(f'排序前的数组顺序: {num_list}')
bubbleSortOptimize2(num_list)
print(f'排序后的数组顺序: {num_list}')
控制台输出
排序前的数组顺序: [1, 3, 2, 4, 5, 6]
第 1 轮 第 1 次 比较 1 和 3 不交换位置[1, 3, 2, 4, 5, 6]
第 1 轮 第 2 次 比较 3 和 2 交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 3 次 比较 3 和 4 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 4 次 比较 4 和 5 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮 第 5 次 比较 5 和 6 不交换位置[1, 2, 3, 4, 5, 6]
第 1 轮排序结果: [1, 2, 3, 4, 5, 6]
最后交换的位置: 1
第 2 轮 第 1 次 比较 1 和 2 不交换位置[1, 2, 3, 4, 5, 6]
第 2 轮排序结果: [1, 2, 3, 4, 5, 6]
排序后的数组顺序: [1, 2, 3, 4, 5, 6]