第2讲. 冒泡思想

冒泡是指在一个区间从一端往另一端进行相邻位置的比较交换，可以实现将该区间的最值顶到另一端。

1. 从后往前冒泡

列表 a 中存放着一些整数，使用冒泡的方法将最小数调整到最前面。

for i in range(len(a)-1,0,-1):
    if a[j-1]>a[j]:
        a[j-1],a[j] = a[j],a[j-1]

2. 冒泡排序：不断减少未定区间的排序思想

（1）从后往前冒泡

n = len(a)
for i in range(n-1):
    # 未定区间[i,n-1] 
    for j in range(n-1,i,-1):
        if a[j-1]>a[j]:
            a[j-1],a[j] = a[j],a[j-1]

（2）从前往后冒泡

n = len(a)
for i in range(n-1):
    #  未定区间[0,n-1-i] n-1-i 是 i 的对称位置
    for j in range(n-1-i):
        if a[j]>a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]

3. 冒泡排序优 1：发现有序（冒泡不交换），及时结束

n = len(a)
for i in range(n-1):
    # 未定区间[i,n-1] 
    f = False
    for j in range(n-1,i,-1):
        if a[j-1]>a[j]:
            a[j-1],a[j] = a[j],a[j-1]
            f = True
    if not f: break

4. 冒泡排序优化 2：记录最后交换位置

n = len(a); i = 0
while i<n-1:
    p = n
    for j in range(n-1,i,-1):
        if a[j-1]>a[j]:
            a[j-1],a[j]=a[j],a[j-1]
            p = j
    i = p

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