冒泡排序

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)