Python 练习
1. 题目
假如有 10 个小盆友从左到右站成一排，个头不等。老师想让他们按照个头从低到高站好。
第一个小盆友只有一个人我们假设是有序的，然后第二个小盆友会跟第一个比，如果第一个高就交换位置。
接下来第三个小盆友从第二个位置开始比较，如果没第二个高就交换位置，然后没第一个高也交换位置，保持前边三个小盆友身高有序就好。
依次类推，等到最后一个小盆友也转移到合适的位置，整个队列就是有序的了。
2. 分析
插入排序
3. 实例
import random
def insertion_sort(seq):
""" 每次挑选下一个元素插入已经排序的数组中,初始时已排序数组只有一个元素"""
n = len(seq)
for i in range(1, n):
value = seq[i] # 保存当前位置的值，因为转移的过程中它的位置可能被覆盖
# 找到这个值的合适位置，使得前边的数组有序 [0,i] 有序
pos = i
while pos > 0 and value < seq[pos-1]:
seq[pos] = seq[pos-1] # 如果前边的元素比它大，就让它一直前移
pos -= 1
seq[pos] = value # 找到了合适的位置赋值就好
print(f"第{i}轮：", seq)
seq = list(range(10))
random.shuffle(seq)
print("原 始：", seq)
insertion_sort(seq)