Python 实现插入排序

插入排序适合于部分有序序列和小规模的数据。其平均时间复杂度为 O(N^2)，空间复杂度为 O(1)，并且为稳定排序。

插入排序将待排序序列分为有序区 (记为 S 区)和无序区(记为 R 区)。以从小到大的顺序为例，每次从 R 区弹出一个元素 O，要将元素 O 插入到 S 区中恰当位置。从 S 区最右端开始，依次比较 S 区元素与元素 O 的大小。如果元素O 比 S 区元素小，就将 S 区元素后移一位。如果元素 O 大于 S 区元素，就在该元素右边一位插入元素 O。

import random

# Python高效编程
def insertionSort(sequence):
    seq = sequence[:]
    for i in range(1, len(seq)):
        value = seq[i]
        j = i - 1
        while j >= 0 and seq[j] > value:
            seq[j+1] = seq[j]
            j -= 1
        # j 在上面多减了 1，要加回来
        seq[j+1] = value
    return seq

random.seed(520)
seq = [random.randint(1, 100) for _ in range(12)]
print(seq)
print(insertionSort(seq))
#[2, 8, 51, 52, 18, 58, 56, 98, 54, 27, 32, 50]
#[2, 8, 18, 27, 32, 50, 51, 52, 54, 56, 58, 98]