区块链技术博客
www.b2bchain.cn

Python经典算法(小白入门系列)——插入排序

这篇文章主要介绍了Python经典算法(小白入门系列)——插入排序的讲解,通过具体代码实例进行23290 讲解,并且分析了Python经典算法(小白入门系列)——插入排序的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=23290

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

      • 1.插入排序的原理
      • 2.分拆插入排序的步骤
      • 3.插入排序——完整代码(升序)
      • 4. 插入排序—-倒序
      • 5.时间复杂度

1.插入排序的原理

  • 通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入
  • 插入排序核心:假设第一个元素排好,之后的元素对排好的部分从后向前比较并逐一移动比较

Python经典算法(小白入门系列)------插入排序

Python经典算法(小白入门系列)------插入排序

 def insertionSort(arr):         for i in range(1, len(arr)):             key = arr[i]             j = i-1         while j >=0 and key < arr[j] :                  arr[j+1] = arr[j]                  j -= 1         arr[j+1] = key        arr = [12, 11, 13, 5, 6]  insertionSort(arr)  print ("排序后的数组:")  for i in range(len(arr)):      print ("%d" %arr[i])  
  • 以上内容来源:Python 插入排序
  • 如果你完全看懂了,说明优秀的你不用继续往下看了;如果看着感觉还是一脸懵逼,建议试着往下看看,我尽最大能力把这个说的简单一些!

2.分拆插入排序的步骤

 my_list = [12, 11, 4]  

使用插入排序的思想,将以上列表最后一个元素4,按照升序的方式对列表排序

  • 最后一个值是固定的值,任何时候我们取它的时候,都不能变动。因为我们需要和前面2个值比较2次,也就是需要取这个固定的值2次,然后根据情况,选择插入具体哪个位置
  • 如上列表中,11比4大,那么11肯定要放在最后一个位置。而我们如果使用my_list[i]这种方式取4的值,那么那么第一轮比较之后,我们需要的固定的值4就变为11了。所以需要把固定的值4用一个临时变量保存一下,暂且用temp = 4表示
  • 第一轮比较完的结果是应该是[12, 4, 11] ,temp = 4, 如果两两比较就直接调换位置,那就成了冒泡排序了。插入排序的特点是只比较,最后一步才插入固定值4的位置。所以目前的结果是[12, 11, 11], temp = 4;
  • 第二轮,用12 和 4 比较,因为12 > 4 ,所以12赋值给到上一个索引的位置,变为[12, 12, 11], temp = 4;
  • 第三轮,发现索引0的地方后面没值了。就不比较了,直接把temp = 4 赋值给最后一个索引0即可。
 my_list = [12, 11, 4] n = len(my_list) index = n - 1							# 此处为了获取最后一个索引,即被插入元素的索引 temp = my_list[index]					# 将这个被插入的元素,保存为一个临时变量,方便后续对比 j = index - 1							# j索引的位置,所有需要被比较元素的第一个位置,从右向左依次比较的 while temp < my_list[j] and j >= 0:		# j是被比较元素的索引     my_list[j + 1] = my_list[j]			# 这一步可以理解为,把被比较的元素,往前移动一个位置     print("---->", my_list, '--->', j)     j -= 1 my_list[j + 1] = temp					# 如上while循环中,j-=1不符合的时候,就跳出了循环,那上一个索引就是需要插入的地方 print(my_list)  
 ----> [12, 11, 11] ---> 1 ----> [12, 12, 11] ---> 0 [4, 12, 11]  
  • 以上内容仅仅为了说明,4这个元素,如果通过插入排序变为[4, 12, 11]的,不是列表的排序,关注4的位置变化即可
  • 通过以上发现,最外层如果有个循环用来找到4元素的索引,告诉内循环那个元素是将要插入的元素。然后从1开始,一直到列表的最后一个索引。
  • 内循环,直接用上面的原理,就能从左向右,依次把元素一个一个的插入到合适的位置。

3.插入排序——完整代码(升序)

 my_list = [12, 11, 4, 8, 2, 1, 9, 6] n = len(my_list) for i in range(1, n):			# 从第二个元素开始,被选为插入元素的索引     temp = my_list[i]			# 找到外层循环的,对应的具体的插入元素的值     j = i - 1     while temp < my_list[j] and j >= 0:         my_list[j + 1] = my_list[j]         print("---->", my_list, '--->', j)         j -= 1     my_list[j + 1] = temp     print("==", my_list) print(my_list)  
 ----> [12, 12, 4, 8, 2, 1, 9, 6] ---> 0 == [11, 12, 4, 8, 2, 1, 9, 6] ----> [11, 12, 12, 8, 2, 1, 9, 6] ---> 1 ----> [11, 11, 12, 8, 2, 1, 9, 6] ---> 0 == [4, 11, 12, 8, 2, 1, 9, 6] ----> [4, 11, 12, 12, 2, 1, 9, 6] ---> 2 ----> [4, 11, 11, 12, 2, 1, 9, 6] ---> 1 == [4, 8, 11, 12, 2, 1, 9, 6] ----> [4, 8, 11, 12, 12, 1, 9, 6] ---> 3 ----> [4, 8, 11, 11, 12, 1, 9, 6] ---> 2 ----> [4, 8, 8, 11, 12, 1, 9, 6] ---> 1 ----> [4, 4, 8, 11, 12, 1, 9, 6] ---> 0 == [2, 4, 8, 11, 12, 1, 9, 6] ----> [2, 4, 8, 11, 12, 12, 9, 6] ---> 4 ----> [2, 4, 8, 11, 11, 12, 9, 6] ---> 3 ----> [2, 4, 8, 8, 11, 12, 9, 6] ---> 2 ----> [2, 4, 4, 8, 11, 12, 9, 6] ---> 1 ----> [2, 2, 4, 8, 11, 12, 9, 6] ---> 0 == [1, 2, 4, 8, 11, 12, 9, 6] ----> [1, 2, 4, 8, 11, 12, 12, 6] ---> 5 ----> [1, 2, 4, 8, 11, 11, 12, 6] ---> 4 == [1, 2, 4, 8, 9, 11, 12, 6] ----> [1, 2, 4, 8, 9, 11, 12, 12] ---> 6 ----> [1, 2, 4, 8, 9, 11, 11, 12] ---> 5 ----> [1, 2, 4, 8, 9, 9, 11, 12] ---> 4 ----> [1, 2, 4, 8, 8, 9, 11, 12] ---> 3 == [1, 2, 4, 6, 8, 9, 11, 12] [1, 2, 4, 6, 8, 9, 11, 12]  

4. 插入排序—-倒序

 my_list = [12, 11, 4, 8, 2, 1, 9, 6] n = len(my_list) for i in range(1, n):     temp = my_list[i]     j = i - 1     while temp > my_list[j] and j >= 0:			# 其实只需要改动的是temp > my_list[j]即可         my_list[j + 1] = my_list[j]         print("---->", my_list, '--->', j)         j -= 1     my_list[j + 1] = temp     print("==", my_list) print(my_list)   

5.时间复杂度

  • 在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为 O(n)

  • 最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为 O(n^2)

  • 平均来说,A[1…j-1]中的一半元素小于A[j],一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样,是输入规模的二次函数

空间复杂度
插入排序的空间复杂度为常数阶O(1)

本文转自互联网,侵权联系删除Python经典算法(小白入门系列)——插入排序

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Python经典算法(小白入门系列)——插入排序
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们