排序算法(三):插入排序-阿里云开发者社区

开发者社区> 人工智能> 正文

排序算法(三):插入排序

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

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

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

算法过程

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

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

演示示例

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

初始状态为:

img_b2bc34f99648552229494a1aaba73935.png

根据算法过程:

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

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

img_c526523905fe955e3b7951bbadff486f.png

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

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

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

img_15097ba7b6a39c2004c9be5eda01e02f.png

...
...
...

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

img_44744bdc60e093a5825ca080f6ee7e1f.png

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

算法示例

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
代码分析 :
  • 以上代码中,第一层循环为需要进行的迭代次数,元素个数为 N 的集合,最多需要 N-1 次迭代即可完成排序;
  • 嵌套循环作用是比较并交换新元素与已排序集合中元素位置。

算法分析

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

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

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

github 链接:插入排序

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章