第4讲. 插入排序思想：不断增加有序区间的思想

插入排序模型：一个有序区间，将一个元素加入到有序区间并保持新区间继续有序。初始有序区间只包含 一个元素，不断增加有序区间，直到有序区间包含所有元素。

1. 冒泡式插入

有序区间旁边有一个待插入元素，从该元素往有序区间方向冒泡可以实现有序插入。 [有序区间]待插入元素 或 待插入元素[有序区间] 列表 a 中存放着一些整数，实现列表 a 的升序排序。

（1）有序区间在前

n = len(a)
for i in range(1,n):
    # 有序区间[0,i-1],i 
    for j in range(i,0,-1):
        if a[j-1]>a[j]:
            a[j-1],a[j] = a[j],a[j-1]
        else: break

（2）有序区间在后

n = len(a)
for i in range(n-2,-1,-1):
    #  i,有序区间[i+1,n-1]
    for j in range(i,n-1):
        if a[j]>a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]
        else: break

2. 移位式插入，有序区间在前

（1）常规写法

n = len(a)
for i in range(1,n):
    # 有序区间[0,i-1],i
    t = a[i]
    j = i-1 # j 是数据位 j+1 是空位
    while j>=0 and a[j]>t:
        a[j+1]=a[j] ; j -= 1 
    a[j+1] = t

（2）变化适应：

n = len(a)
for i in range(1,n):
    # 有序区间[0,i-1],i
    t = a[i]
    j = i # j 是空位，j-1 是数据位
    while j>0 and a[j-1]>t:
        a[j] =a [j-1] ; j -= 1
    a[j] = t

（3）移位式插入内循环为什么不用 for 实现。

注意：for 语句是遍历，循环自然结束后变量变量的值为最后遍历的元素； while 是循环，循环自然结束后 一定是不满足循环的条件了。

for i in range(5):
    #...
    print(i)

i = 0
while i < 5:
    #...
    i += 1
print(i)

3. 擂台式插入

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

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