![img_04a54b6e0037dbc24cba17e708c0a8c3.jpe](https://yqfile.alicdn.com/img_04a54b6e0037dbc24cba17e708c0a8c3.jpeg?x-oss-process=image/resize,w_1400/format,webp)
插入排序算法维护一个已排序集合和一个待排序集合,每轮迭代,从待排序集合中选择一个元素,插入到已排序集合中的适当位置,通过多次迭代,最终完成排序。
冒泡排序 是通过在待排序集合中,进行不断的比较和交换元素位置来确定极值,然后标记该极值为已排序。选择排序 是通过比较待排序集合中的元素大小来确定极值位置,然后交换元素位置,构成已排序元素。插入排序的不同之处在于,它是顺序选择待排序集合中元素,依次添加到已排序集合中的适当位置上。所以插入排序的操作主要作用于已排序集合上,而非待排序集合。
算法过程
以递增排序为例,初始已排序集合只有第一个元素,其后元素构成初始待排序集合
- 选择待排序集合中第一个元素作为新元素,从右向左遍历交换新元素与其左边的元素,直到新元素的值不小于其左边元素的值;
- 标记该新元素为已排序;
- 重复步骤 1,2,直到待排序集合为空
演示示例
初始状态:0 次排序
已排序集合:[6]
待排序集合:[3, 4, 0, 2, 1, 8, 5, 9, 7]
初始状态为:
![img_b2bc34f99648552229494a1aaba73935.png](https://yqfile.alicdn.com/img_b2bc34f99648552229494a1aaba73935.png?x-oss-process=image/resize,w_1400/format,webp)
根据算法过程:
- 步骤一,选择待排序集合的第一个元素 3,比较 3 与其左边的元素 6 并交换位置;
- 步骤二,标记元素 3 为已排序
1 次排序后
已排序集合:[3, 6]
待排序集合:[4, 0, 2, 1, 8, 5, 9, 7]
![img_c526523905fe955e3b7951bbadff486f.png](https://yqfile.alicdn.com/img_c526523905fe955e3b7951bbadff486f.png?x-oss-process=image/resize,w_1400/format,webp)
根据算法过程步骤三,待排序集合不为空,所以重复执行步骤一、二:
- 步骤一,选择待排序集合的第一个元素 4,比较 4 与其左边的元素 6 并交换位置,然后比较 4 与其左边的元素 3;
- 步骤二,标记元素 4 为已排序
2 次排序后
已排序集合:[3, 4, 6]
待排序集合:[0, 2, 1, 8, 5, 9, 7]
![img_15097ba7b6a39c2004c9be5eda01e02f.png](https://yqfile.alicdn.com/img_15097ba7b6a39c2004c9be5eda01e02f.png?x-oss-process=image/resize,w_1400/format,webp)
...
...
...
9 次排序后
已排序集合:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
待排序集合:[]
![img_44744bdc60e093a5825ca080f6ee7e1f.png](https://yqfile.alicdn.com/img_44744bdc60e093a5825ca080f6ee7e1f.png?x-oss-process=image/resize,w_1400/format,webp)
观察以上过程可知,每次排序后待排序集合元素数减一,即每一次排序形成一个已排序元素。 个元素的序列,初始待排序集合元素数为
,所以经过
次排序后,待排序集合为空,即完成排序。
算法示例
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。
算法执行过程中,不需要申请额外的序列空间来保存临时元素,属于原地排序方式,所以算法的空间复杂度为 。
github
链接:插入排序