• 21天学习挑战:经典算法---插入排序


    活动地址:CSDN21天学习挑战赛

    21天学习挑战:经典算法---插入排序

    插入排序

    插入排序介绍

    插入排序得基本思路是每次插入一个元素,每一趟完成对待插入元素得放置,直到全部插入完成。

    • 直接插入排序
      直接插入排序是一种最简单得排序方法,过程就是将每个待排元素逐个插入到已经排号得有序序列中。

    • 折半插入排序
      由于在插入排序的过程中,已经生成了一个(排好的元素组成)有序数列。所以插入待排元素时可以使用折半查找的方式,更快速的确定新元素的位置,当元素个数较多时,折半插入排序优于直接插入排序。

    • 希尔排序
      希尔排序可以看作是分组排序的排序方法。把全部元素分成几组(等距元素分到一组),在每一组内进行直接插入排序。然后继续减少间距,形成新的分组,进行排序,直到间距为1时停止。

    直接插入排序

    • 输入
      n个数的序列,通常直接存放在数组中,可能是任何顺序

    • 输出
      输入序列的一个新排列,满足从小到大的顺序,默认升序,简单修改可以实现降序

    • 算法说明
      每次从原有数据中取出一个数,插入到之前已经排好的序列中,直到所有的数全部取完,那么新的有序排列也就完成了。
      通俗一点的解释就好比我们在打扑克牌,所有的牌扣在桌面上,我们一张一张的抓,抓起一张就在手里把它排好,那么我们把所有的牌都抓起来之后,手里的牌也就是有序的了

    • 算法流程
      对于计算机来说,我们必须要详细的告诉它如何比较大小,以及如何确定位置,毕竟它不能像我们一样,一眼就看出位置。试想一下,当数据量比较多的时候,我们也需要一个一个的看过来,然后才能确定新插入元素的位置,整个过程如下:
      1 第一个元素:放在第一个位置,直接排好
      2 第二个元素: 与第一个元素比较,如果更大,放在第二个位置,如果更小,放在第一个位置
      3 第三个元素:顺次从后向前比较,如果更小,将已排好的元素向后串位,直到找到合适的位置插入
      4 剩余其它元素: 顺次从后向前比较,如果更小,将已排好的元素向后串位,直到找到合适的位置插入
      5 如果待排元素是已经排好元素中最大的,只需要比较一次,然后直接追加到已排好的序列后面

    直接插入排序伪代码

    for j=2 to A.length
    	key = A[j]
    	i=j-1
    	while i>0 and A[i]>key
    		A[i+1]=A[i]
    		i = i -1 
    	A[i+1] = key
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    初始计数器为2 , 代表第一个元素默认排好,从第二个元素开始操作,直到最后一个元素
    每次用key记录新操作的元素,i的初始值代表当前操作元素的前一个元素,也就是第一个要与之比较的元素。
    while循环为内层循环,作用是已经排号的元素中找到合适的位置,来将key插入。
    如果进入到循环体中执行,代表key相对较小,还要再向前寻找,同时,与之比对的元素要向后串位,因为此时可以确定,key一定在这个for循环的最后一行是将key插入到对应的位置,外层循环结束(每次循环插入一个数)

  • 相关阅读:
    【Python 实战基础】Pandas如何对Categorical类型字段数据统计
    Lesson 02 类与对象 (终)
    Day716. 抛出异常是一个合适的选择吗? -Java8后最重要新特性
    悬镜云鲨SaaS三大核心能力 构筑下一代积极防御体系
    STM32实现0.96寸OLED显示模拟IIC和IIC四种实现(标准库和HAL库)
    个人练习-PAT甲级-1143 Lowest Common Ancestor
    【SSM进阶学习系列丨整合篇】Spring+SpringMVC+MyBatis 框架配置详解
    冰冰学习笔记:初识环境变量
    E - Stoned Game
    计算狗携手成都超算中心和重庆大学,共同助力“碳中和”
  • 原文地址:https://blog.csdn.net/qq_32761549/article/details/126153316