"""

File: bubble_sort.py

Created Time: 2022-11-25

Author: timi (xisunyy@163.com)

"""

def bubble_sort(nums: list[int]):

"""冒泡排序"""

n = len(nums)

# 外循环：未排序区间为 [0, i]

for i in range(n - 1, 0, -1):

# 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端

for j in range(i):

if nums[j] > nums[j + 1]:

# 交换 nums[j] 与 nums[j + 1]

nums[j], nums[j + 1] = nums[j + 1], nums[j]

def bubble_sort_with_flag(nums: list[int]):

"""冒泡排序（标志优化）"""

n = len(nums)

# 外循环：未排序区间为 [0, i]

for i in range(n - 1, 0, -1):

flag = False # 初始化标志位

# 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端

for j in range(i):

if nums[j] > nums[j + 1]:

# 交换 nums[j] 与 nums[j + 1]

nums[j], nums[j + 1] = nums[j + 1], nums[j]

flag = True # 记录交换元素

if not flag:

break # 此轮冒泡未交换任何元素，直接跳出

"""Driver Code"""

if __name__ == "__main__":

nums = [4, 1, 3, 1, 5, 2]

bubble_sort(nums)

print("冒泡排序完成后 nums =", nums)

nums1 = [4, 1, 3, 1, 5, 2]

bubble_sort_with_flag(nums1)

print("冒泡排序完成后 nums =", nums1)