import random
a = [2,1,3,5,4]

# a.sort()#排序原来的数列
#b = sorted(a) #不改变原来的顺序，返回排序好的列表
# random.shuffle(a)#随机打乱

# print(a)

#冒泡排序 ： 核心是两两交换
n = len(a)
# for i in range(n-1):
#   for j in range(n-2,i-1,-1):
#       if a[j] > a[j+1]:
#           a[j],a[j+1] =a[j+1],a[j]

# print(a)

#冒泡改进

# flag = True
# k = n
# while flag:
#   flag = False
#   for i in range(k-1):
#       if a[i] > a[i+1]:
#           a[i], a[i+1]=  a[i+1],a[i]
#           flag = True
#   k -= 1
# print(a)


#冒泡改进2
pos = n
while pos > 0 :
    k = pos
    pos = 0
    for i in range(k-1):
        if a[i] > a[i+1]:
            a[i],a[i+1]=a[i+1],a[i]
            pos = i+1
print(a)

#双向冒泡：思考如何实现？

方法1：
for i in range(n//2):
    #从左到右
    for j in range( i,n-1-i ):
        if a[j] > a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]
    #从右到左 
    for j in range(n-2-i ,i,-1 ):
        if a[j] > a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]
print(a)

方法2：
def bidirectional_bubble_sort(arr):
    n = len(arr)
    left, right = 0, n - 1

    while left < right:
        # 从左向右冒泡
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]

        # 缩小右边界
        right -= 1

        # 从右向左冒泡
        for j in range(right, left, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]

        # 扩大左边界
        left += 1
def bidirectional_bubble_sort_optimized(arr):
    n = len(arr)
    left, right = 0, n - 1

    while left < right:
        last_swap_left = 0
        # 从左向右冒泡
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap_left = i

        # 缩小右边界
        right = last_swap_left

        last_swap_right = n - 1
        # 从右向左冒泡
        for j in range(right, left, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                last_swap_right = j

        # 扩大左边界
        left = last_swap_right

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com