Python数据结构与算法(14)---插入排序
【摘要】
目录
插入排序图解插入排序实战:插入排序
插入排序
插入排序,又名Insertion Sort,其原理是数列前面为排序完成的值,数列后面为未排序的值。
假设前面n-1(其中 n&g...
插入排序
插入排序,又名Insertion Sort,其原理是数列前面为排序完成的值,数列后面为未排序的值。
假设前面n-1(其中 n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。
图解插入排序
原理过程如下:
- 输入n个数值的列表
- 接着,进行下标0和1的数值比较,把大的放后面,小的插入到前面,第1轮排序结束(其前2位为排序完成的数列,后面n-2个为未排序的数列)
- 继续选择下标为的数值和下标为1的数值进行比较,大的后移1位,小的继续比较小标0的位置,大的后移,小的插入前面。
- 依次类推,直到n-1下标的数值插入完成,获得最终的排序结果。
图解插入排序:
第1次循环(i=1,j=1):
第2次循环(i=2,j=2):
第3次循环(i=3,j=3):
第4次循环(i=4,j=4):
第5次循环(i=5,j=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)