十大排序算法之三：插入排序(Python)-白红宇的个人博客

发布日期：2021-05-08 01:39:59 浏览次数：7 分类：精选文章

本文共 820 字，大约阅读时间需要 2 分钟。

一、插入排序简介

插入排序之所以叫插入排序，是因为它的排序方式是不断从未排序序列中取出一个数，插入到已排序序列的合适位置。就像是数组插入一样，需要不断的移动数据，如果要插入的这个数是在已排序的序列中间的话，就需要从中间往后的数据依次后后移一个位置，给新插入的元素腾位置。

它的原理是先构建一个有序序列，对于未排序数据，在已排序序列中从后向前扫面，找到对应位置并且插入。

二、插入排序步骤

1：首先把序列中的第一个元素看作是已排序序列，把第二个元素一直到最后一个元素看作是未排序序列。

2：从头到尾依次扫描未排序序列，将扫描到的元素插入到有序序列的合适位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)

那么：怎么将扫描到的元素 a 插入到有序序列的合适位置呢？

这就需要我们从尾到头依次扫描已排序序列，让a依次和它们比较，如果他它们大于a，就后移一个单位。以此类推，直到找到合适的位置。

三、代码实现

def InsertionSort(arr):    for i in range(len(arr)):        current=arr[i] #用current把a[i]的值临时存下来，要不然之后比较数据往后移动时会把arr[i]的值覆盖掉        perIndex=i-1        while perIndex>=0 and arr[perIndex]>current:            arr[perIndex+1]=arr[perIndex]            perIndex -= 1        arr[perIndex+1]=current    return arrif __name__=='__main__':    array=[3,44,38,5,15,36,46,2,48,19]    print(InsertionSort(array))

在这里插入图片描述

上一篇：C语言结构体与C++中类的区别

下一篇：十大排序算法之二：选择排序(Python)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章