Python数据结构与算法(14)---插入排序

举报
择城终老 发表于 2021/09/01 22:19:28 2021/09/01
【摘要】 目录 插入排序图解插入排序实战:插入排序 插入排序 插入排序,又名Insertion Sort,其原理是数列前面为排序完成的值,数列后面为未排序的值。 假设前面n-1(其中 n&g...

头图

插入排序

插入排序,又名Insertion Sort,其原理是数列前面为排序完成的值,数列后面为未排序的值。

假设前面n-1(其中 n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

图解插入排序

原理过程如下:

  1. 输入n个数值的列表
  2. 接着,进行下标0和1的数值比较,把大的放后面,小的插入到前面,第1轮排序结束(其前2位为排序完成的数列,后面n-2个为未排序的数列)
  3. 继续选择下标为的数值和下标为1的数值进行比较,大的后移1位,小的继续比较小标0的位置,大的后移,小的插入前面。
  4. 依次类推,直到n-1下标的数值插入完成,获得最终的排序结果。

图解插入排序:

第1次循环(i=1,j=1):

循环1
第2次循环(i=2,j=2):

循环2
第3次循环(i=3,j=3):

循环3
第4次循环(i=4,j=4):

循环4
第5次循环(i=5,j=5):

循环5

实战:插入排序

既然,我们即说明了其原理,又图解了其原理,相信读者对这个算法应该非常了解了。下面,我们使用Python来实现插入排序算法,示例如下:

def insert_sort(my_list):
    if len(my_list) == 1:
        return my_list
    for i in range(1, len(my_list)):
        temp = my_list[i]
        j = i
        while j > 0 and my_list[j - 1] > temp:
            my_list[j] = my_list[j - 1]
            j -= 1
        my_list[j] = temp
    return my_list


if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("排序前的数组:", my_list)
    print("排序后的数组:", insert_sort(my_list))

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

运行之后,效果如下:

最终效果

文章来源: liyuanjinglyj.blog.csdn.net,作者:李元静,版权归原作者所有,如需转载,请联系作者。

原文链接:liyuanjinglyj.blog.csdn.net/article/details/120024286

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。