排序算法（三）：插入排序

插入排序算法维护一个已排序集合和一个待排序集合，每轮迭代，从待排序集合中选择一个元素，插入到已排序集合中的适当位置，通过多次迭代，最终完成排序。

冒泡排序是通过在待排序集合中，进行不断的比较和交换元素位置来确定极值，然后标记该极值为已排序。选择排序是通过比较待排序集合中的元素大小来确定极值位置，然后交换元素位置，构成已排序元素。插入排序的不同之处在于，它是顺序选择待排序集合中元素，依次添加到已排序集合中的适当位置上。所以插入排序的操作主要作用于已排序集合上，而非待排序集合。

算法过程

以递增排序为例，初始已排序集合只有第一个元素，其后元素构成初始待排序集合

选择待排序集合中第一个元素作为新元素，从右向左遍历交换新元素与其左边的元素，直到新元素的值不小于其左边元素的值；
标记该新元素为已排序；
重复步骤 1,2，直到待排序集合为空

演示示例

初始状态：0 次排序
已排序集合：[6]
待排序集合：[3, 4, 0, 2, 1, 8, 5, 9, 7]

初始状态为：

根据算法过程：

步骤一，选择待排序集合的第一个元素 3，比较 3 与其左边的元素 6 并交换位置；
步骤二，标记元素 3 为已排序

1 次排序后
已排序集合：[3, 6]
待排序集合：[4, 0, 2, 1, 8, 5, 9, 7]

根据算法过程步骤三，待排序集合不为空，所以重复执行步骤一、二：

步骤一，选择待排序集合的第一个元素 4，比较 4 与其左边的元素 6 并交换位置，然后比较 4 与其左边的元素 3；
步骤二，标记元素 4 为已排序

2 次排序后
已排序集合：[3, 4, 6]
待排序集合：[0, 2, 1, 8, 5, 9, 7]

...
...
...

9 次排序后
已排序集合：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
待排序集合：[]

观察以上过程可知，每次排序后待排序集合元素数减一，即每一次排序形成一个已排序元素。 $N$ 个元素的序列，初始待排序集合元素数为 $N-1$ ，所以经过 $N-1$ 次排序后，待排序集合为空，即完成排序。

算法示例

def insertionSort(arr):
    for i in range(1, len(arr)):  # 迭代次数
        tmp, j = arr[i], i
        while j > 0 and tmp < arr[j - 1]:
            arr[j] = arr[j - 1]
            j = j - 1
        arr[j] = tmp

代码分析：

以上代码中，第一层循环为需要进行的迭代次数，元素个数为 $N$ 的集合，最多需要 $N-1$ 次迭代即可完成排序；
嵌套循环作用是比较并交换新元素与已排序集合中元素位置。

算法分析

插入排序是一种稳定排序算法，排序过程中，如果两个元素值相等，则不交换元素位置。对于 $N$ 个元素的序列：

最坏情况下，当序列为逆序时，每一次迭代过程中，都需要比较并交换新元素与其左边的所有元素位置，即第 $i$ 次迭代，新元素左边的元素个数为 $i+1$ ，所以最坏情况下，算法的交换复杂度和比较复杂度都为 $O(n^2)$ ;
最好情况下，当序列为已排序时，每一次迭代过程中，只需要做一次比较即可，所以最好情况下，算法的比较复杂度为 $O(n)$ ，交换复杂度为 0。

算法执行过程中，不需要申请额外的序列空间来保存临时元素，属于原地排序方式，所以算法的空间复杂度为 $O(1)$ 。

github 链接：插入排序