直接插入排序
作者:尹正杰
版权声明:原创作品,谢绝转载!否则将追究法律责任。
一.直接插入排序(Direct insertion sort)概述
在为排序序列中,构建一个子排序序列,直至全部数据排序完成
将代排序的数,插入到已经排序的序列中合适的位置
增加一个哨兵,放入比较值,让它和后面已经排好的序列比较,找到合适的插入点
二.直接插入排序原理
初始值:[1 9 8 5 6] 第一趟:[0 1 9 8 5 6] [9 1 9 8 5 6] -> [1 9 8 5 6] #如大家所看到的,和初始值必须,我在第一个位置上增加了一个数字0,这个数字0的位置我们称其为哨兵,接下来我们直接取初始值的第二个索引9和它前面一个索引比较(第一个索引相比较),哨兵9比1大,则不需要交换位置,本轮比较结束。
第二趟:[8 1 9 8 5 6] [8 1 ? 9 5 6] [8 1 8 9 5 6] -> [1 8 9 5 6] #拿到上一轮比赛结果,接下来我们直接取初始值的第三个索引8和它前面一个索引比较,本轮哨兵为8,而哨兵8比9小,因此,我们需要把9往右移动一位,此时哨兵被插入8和9交换位置索引变为第二个索引,此时依旧需要和前面的一个索引进行比较,很显然第一个索引为1,而哨兵为8,哨兵8比1大,则不需要交换位置,本轮比赛结束。(简单的说就是如果比本轮哨兵大就相互交换位置,如果比本轮哨兵小则本轮结束)
第三趟:[5 1 8 9 5 6] [5 1 8 ? 9 6] [5 1 ? 8 9 6] [5 1 5 8 9 6] -> [1 5 8 9 6] #拿到上一轮比赛结果,接下来我们直接去初始值的第四个索引5和它前面一个索引比较,本轮哨兵为5,而哨兵5比9小,因此他们需要相互交换位置,接着哨兵5再和它前面一个索引比较,哨兵5比8小,继续交换位置,然后继续和它前面一个索引比价,发现哨兵5比1大,终止本轮比赛。
第四趟:[6 1 5 8 9 6] [6 1 5 8 ? 9] [6 1 5 ? 8 9] [6 1 5 6 8 9] -> [1 5 6 8 9] #拿到上一轮的结果,继续重复插入排序比较,经过上面3次比较,想必大家也清楚它是如何排序的了,最终经过四趟比较,得到的排序是:1 5 6 8 9
三.使用Python代码实现直接插入排序
1 #!/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/ 5 #EMAIL:y1053419035@qq.com 6 7 """ 8 思路: 9 增加一个哨兵位,每轮比较将比较数放入 10 哨兵依次和前一个数据比较,大数靠右移动,找到哨兵中值的插入位置 11 每一轮结束后,得到一个从开始到待比较数位置的一个有序序列 12 13 插入排序特点: 14 最好情况,正好是升序排列,比较迭代n-1次 15 最差情况,正好是降序排列,比较迭代1,2,...,n-1即 n(n-1)/2 16 使用两次嵌套循环,时间复杂度O(n^2) 17 稳定排序算法 18 使用在小规模数据比较 19 待优化: 20 如果比较操作耗时大的话,可以采用二分查找提高效率,即二分查找插入排序 21 22 """ 23 24 m_list = [ 25 [1,9,8,5,6,7,4,3,2], 26 [1,2,3,4,5,6,7,7,9], 27 [9,8,7,6,5,4,3,2,1], 28 [1,1,1,1,1,1,1,1,2] 29 ] 30 31 nums = [0] + m_list[2] 32 print(m_list[2]) 33 34 sentinel,*origin = nums #哨兵位,待比较数字 35 36 count_swap = 0 37 38 count_iter = 0 39 40 length = len(nums) 41 42 for i in range(2,length): #从2开始 43 nums[0] = nums[i] #放置哨兵 44 j = i - 1 45 count_iter += 1 46 if nums[j] > nums[0]: #大数右移,找到插入位置 47 while nums[j] > nums[0]: 48 nums[j +1] = nums[j] #依次右移 49 j -= 1 50 count_swap += 1 51 nums[j + 1] = nums[0] #将哨兵插入,注意插入在右侧要+1 52 53 print(nums,count_swap,count_iter) 54 55 56 57 #以上代码执行结果如下: 58 [9, 8, 7, 6, 5, 4, 3, 2, 1] 59 [1, 1, 2, 3, 4, 5, 6, 7, 8, 9] 36 8
当你的才华还撑不起你的野心的时候,你就应该静下心来学习。当你的能力还驾驭不了你的目标的时候,你就应该沉下心来历练。问问自己,想要怎样的人生。 欢迎加入基础架构自动化运维:598432640,大数据SRE进阶之路:959042252,DevOps进阶之路:526991186
今天的文章直接插入排序_冒泡排序示意图分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/54210.html