插入排序算法维护一个已排序集合和一个待排序集合,每轮迭代,从待排序集合中选择一个元素,插入到已排序集合中的适当位置,通过多次迭代,最终完成排序。
冒泡排序 是通过在待排序集合中,进行不断的比较和交换元素位置来确定极值,然后标记该极值为已排序。选择排序 是通过比较待排序集合中的元素大小来确定极值位置,然后交换元素位置,构成已排序元素。插入排序的不同之处在于,它是顺序选择待排序集合中元素,依次添加到已排序集合中的适当位置上。所以插入排序的操作主要作用于已排序集合上,而非待排序集合。
以递增排序为例,初始已排序集合只有第一个元素,其后元素构成初始待排序集合
初始状态:0 次排序 已排序集合:6 待排序集合:3, 4, 0, 2, 1, 8, 5, 9, 7
初始状态为:
根据算法过程:
1 次排序后 已排序集合:3, 6 待排序集合:4, 0, 2, 1, 8, 5, 9, 7
根据算法过程步骤三,待排序集合不为空,所以重复执行步骤一、二:
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。
算法执行过程中,不需要申请额外的序列空间来保存临时元素,属于原地排序方式,所以算法的空间复杂度为
。