python3实现
n个元素需要排n-1趟
# 冒泡排序
num_list = [
[1, 9, 8, 5, 6, 7, 4, 3, 2],
[1, 2, 3, 4, 5, 6, 7, 8, 9]
]
nums = num_list[0]
print(nums)
length = len(nums)
count_swap = 0
count = 0
# bubble sort
for i in range(length):
for j in range(length - i - 1):
count += 1
if nums[j] > nums[j + 1]:
tmp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = tmp
count_swap += 1
print(nums, count_swap, count)
# 输出结果
# [1, 9, 8, 5, 6, 7, 4, 3, 2]
# [1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36
冒泡排序优化
思路
如 ：
[1,2,3,5,4]
第一趟 比较交换后为：
[1,2,3,4,5]
即为所求
此时当第二趟 进行比较时 无元素进行交换即可得知元素已排列好，应退出循环
# 冒泡排序优化
num_list = [
[1, 9, 8, 5, 6, 7, 4, 3, 2],
[1, 2, 3, 4, 5, 6, 7, 8, 9]
]
nums = num_list[1]
print(nums)
length = len(nums)
count_swap = 0
count = 0
# bubble_sort
for i in range(length):
flag = False
for j in range(length - i - 1):
count += 1
if nums[j] > nums[j + 1]:
tmp = nums[j + 1]
nums[j + 1] = nums[j]
nums[j] = tmp
flag = True
count_swap += 1
if not flag:
break
print(nums, count_swap, count)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9] 0 8
注意⚠️：flag=False的位置
冒泡法总结
# 冒泡法需要数据一轮轮比较
# 可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序
# 最差的排序情况，初始顺序与目标顺序完全相反，遍历次数1,…,n-1之和n(n-1)/2
# 最好的排序情况，初始顺序与目标顺序完全相同，遍历次数n-1
# 时间复杂度O(n2)
