欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > IT业 > 数据结构 (31)插入类排序

数据结构 (31)插入类排序

2025/9/21 19:04:05 来源:https://blog.csdn.net/m0_73399576/article/details/144318840  浏览:    关键词:数据结构 (31)插入类排序

前言 

       数据结构中的插入类排序是一种简单直观的排序算法,其核心思想是通过构建有序序列,将未排序的数据逐个插入到已排序的序列中,直到所有元素都排序完毕。

一、基本思想

       插入排序的基本思想是将数组分为已排序和未排序两部分,初始时,已排序部分只包含一个元素,然后依次从未排序部分取出元素,将其插入到已排序部分的适当位置,直到所有元素都插入到已排序部分,排序完成。

二、实现步骤

  1. 初始化
    • 假设数组的第一个元素(或前n-1个元素,当n=1时)已经排序。
    • 从数组的第二个元素开始,依次将其插入到已排序部分的适当位置。
  2. 外层循环
    • 从数组的第二个元素开始遍历到最后一个元素。
  3. 内层循环
    • 取出当前元素(记为key)。
    • 在已排序部分从后向前扫描,找到第一个不大于key的元素的位置。
    • 将扫描过程中大于key的元素向右移动一个位置,为key腾出插入位置。
    • 将key插入到找到的位置。

三、算法复杂度

  1. 时间复杂度
    • 最坏情况:O(n^2),当输入数组是逆序时,每次插入都需要将已排序部分的元素全部向右移动。
    • 最好情况:O(n),当输入数组已经有序时,每次插入都只需要将key放在已排序部分的末尾。
    • 平均情况:O(n^2),因为对于大多数随机生成的数组,插入排序的平均性能接近于最坏情况。
  2. 空间复杂度:插入排序是原地排序算法,其空间复杂度为O(1),因为它只需要一个额外的变量来存储当前要插入的元素。

四、稳定性

       插入排序是稳定的排序算法,即相同关键字的元素在排序后保持原来的相对顺序。这是因为在插入过程中,如果两个元素相等,则不会进行交换操作,从而保持了它们的相对顺序。

五、改进算法

1.希尔排序是插入排序的一种改进算法,也称为递减增量排序。

2.它通过将数组分割成若干个子序列,对每个子序列分别进行插入排序,然后逐渐减小子序列的间隔,直到间隔为1时,对整个数组进行一次插入排序。

3.希尔排序的时间复杂度在O(n^2)和O(n log n)之间,具体取决于间隔序列的选择。

六、应用场景

       插入排序适用于小规模数据集或部分有序的数据集。对于大规模数据集,由于其时间复杂度较高,通常选择更高效的排序算法,如快速排序、归并排序等。然而,在某些特定场景下,如链表排序或需要稳定排序时,插入排序仍然具有一定的应用价值。

总结

       综上所述,插入排序是一种简单直观的排序算法,具有稳定性好、实现简单等优点。然而,其时间复杂度较高,在大规模数据集上性能较差。因此,在选择排序算法时,需要根据具体的应用场景和数据规模来选择合适的算法。

 结语   

当你为错过太阳而哭泣的时候

你也要再错过群星了

!!!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词