直接插入排序_冒泡排序示意图

直接插入排序_冒泡排序示意图直接插入排序 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任。 一.直接插入排序(Direct insertion sort)概述 二.直接插入排序原理 三.使用Python代码实现直接插入排序

直接插入排序_冒泡排序示意图"

                直接插入排序

                                      作者:尹正杰

版权声明:原创作品,谢绝转载!否则将追究法律责任。

 

 

 

一.直接插入排序(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

 

今天的文章直接插入排序_冒泡排序示意图分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/54210.html

(0)
编程小号编程小号
上一篇 2023-08-29
下一篇 2023-08-29

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注