排序算法（三）：插入排序
插入排序算法维护一个已排序集合和一个待排序集合，每轮迭代，从待排序集合中选择一个元素，插入到已排序集合中的适当位置，通过多次迭代，最终完成排序。
冒泡排序 是通过在待排序集合中，进行不断的比较和交换元素位置来确定极值，然后标记该极值为已排序。选择排序 是通过比较待排序集合中的元素大小来确定极值位置，然后交换元素位置，构成已排序元素。插入排序的不同之处在于，它是顺序选择待排序集合中元素，依次添加到已排序集合中的适当位置上。所以插入排序的操作主要作用于已排序集合上，而非待排序集合。
算法过程
以递增排序为例，初始已排序集合只有第一个元素，其后元素构成初始待排序集合
- 选择待排序集合中第一个元素作为新元素，从右向左遍历交换新元素与其左边的元素，直到新元素的值不小于其左边元素的值；
- 标记该新元素为已排序；
- 重复步骤 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 待排序集合：[]
观察以上过程可知，每次排序后待排序集合元素数减一，即每一次排序形成一个已排序元素。
个元素的序列，初始待排序集合元素数为
，所以经过
次排序后，待排序集合为空，即完成排序。
算法示例
def insertionSort(arr):
for i in range(1, len(arr)): # 迭代次数
tmp = arr[i]
while i > 0 and tmp < arr[i - 1]:
arr[i] = arr[i - 1]
i = i - 1
arr[i] = tmp代码分析 ：
- 以上代码中，第一层循环为需要进行的迭代次数，元素个数为
的集合，最多需要
次迭代即可完成排序；
- 嵌套循环作用是比较并交换新元素与已排序集合中元素位置。
算法分析
插入排序是一种稳定排序算法，排序过程中，如果两个元素值相等，则不交换元素位置。对于
个元素的序列：
- 最坏情况下，当序列为逆序时，每一次迭代过程中，都需要比较并交换新元素与其左边的所有元素位置，即第
次迭代，新元素左边的元素个数为
，所以最坏情况下，算法的交换复杂度和比较复杂度都为
;
- 最好情况下，当序列为已排序时，每一次迭代过程中，只需要做一次比较即可，所以最好情况下，算法的比较复杂度为
，交换复杂度为 0。
算法执行过程中，不需要申请额外的序列空间来保存临时元素，属于原地排序方式，所以算法的空间复杂度为
。