基于c语言对插入排序算法的分析研究

王佳林

摘要：数据处理是计算机编程中经常会遇到的问题，而数据排序又是数据处理中的重要组成部分，其中排序算法是数据排序中的核心技术。在很多情况下，排序算法决定着一个程序的执行效率，在实际的编程开发中如何根据具体的问题环境选择合适有效的排序算法就显得尤为重要。本文针对插入排序算法展开研究，对其排序算法原理和特点进行了分析，希望能给相关领域的学者带来帮助。

关键词：c语言;排序算法;直接插入排序;二分查找;希尔排序

随着大数据时代的到来，数据量爆炸式增长，数据排序越显重要。排序好的数据在进行各种操作时都会更加便捷，处理效率也会更高效。排序算法是数据排序的灵魂，决定着所用时间的多少，以及所占空间的大小。下面对基于c语言的插入排序进行详细的分析研究。

一、插入排序的基本原理及分类

（一）插入排序的基本原理

插入排序是内部排序算法的一种，其基本原理是在一次插入操作中，按照排序码的大小，将一个待排序元素插入到一组有序元素的适当位置上去，直到元素全部插入为止。

（二）插入排序的分类

在执行具體插入操作时，根据插入方法的不同，主要分为三种插入排序算法，分别是直接插入排序、带二分查找的直接插入排序和希尔排序。下面对这三种插入排序算法进行详细分析。

二、直接插入排序（Straight Insertion Sort）

（一）直接插入排序的基本思想

直接插入排序的基本思想是在一组待排序的元素中，按一定的顺序取出一个元素，将这个元素按排序码的大小插入到排好序了的元素序列中，进而得到一个新的有序的总元素数目加一的有序表，直到所有的元素都插入到这个有序表中为止。

（二）直接插入排序详细过程及c语言程序代码

下面举例说明，假设有一个N=6个的待排序元素，排序码相同的用*加以区分。其中的临时变量temp起暂存的作用。

（三）直接插入排序算法的性能分析

时间复杂度分析：

初始元素的序列是是影响直接插入排序效率的主要因素，根据初始元素序列的不同其时间复杂度有很大区别。

（1）初始序列是顺序排列时，比较N1次即可完成排序，时间复杂度O（N）。

（2）初始序列是逆序排列时，需比较N*（N1）/2次，时间复杂度O（N^2）。

（3）初始序列杂乱无序时，平均时间复杂度O（N^2）。

空间复杂度分析：

在直接插入排序中，临时变量temp暂存待插入元素，空间复杂度O（1）。

算法稳定性分析：

所谓算法稳定性指的是如果待排序记录中有重复元素，在排序后这些元素的相对位置如果保持不变，那么这个排序算法就是稳定的。反之则不稳定。在图（a）中容易发现排序码相同的记录的相对位置没有变化，可见直接插入排序算法是稳定的排序算法。

（四）直接插入排序的改进

直接插入排序算法在进行位置查找操作中可以进行性能改进，那就是在寻找合适的插入位置时，使用二分查找算法，但插入操作的基本原理不变，这样就可以大大减少元素比较次数，提高算法效率。这种改进之后的算法又叫带二分查找的直接插入排序。

三、希尔排序（Shell Sort）

（一）希尔排序基本原理

希尔排序是在直接插入排序的基础上的一种改进，实际上是将待排序序列分组进行直接插入排序，在分组时会出现增量这个概念，增量其实就是同一组数据中相邻元素的下标相隔距离。希尔排序利用了在数据量小、元素基本有序时直接插入排序的效率高的特点，大大提高了排序的效率。

（二）希尔排序c语言程序代码

（三）希尔排序算法性能分析

时间复杂度分析：

希尔排序算法的时间复杂度分析较复杂，整个过程中元素的比较次数和移动次数因所选择的增量的不同而有较大差异。整体上来看希尔排序的时间复杂度是O（N*logN）。步长gap不同时间复杂度会受影响，根据现有研究随着步长变化希尔排序时间复杂度在O（N*logN）与O（N^2）之间，具体详细的时间复杂度与步长gap的关系还在研究中。

希尔排序算法是不稳定的，这一点在其程序代码中也能发现，在进行分组时两个排序码相同的元素的相对位置可能发生变化。

四、结语

在这个数据时代中，数据处理是经常会遇到的问题，数据排序是数据处理中很重要的一环，研究排序算法具有重要的意义。本文主要研究了基于c语言的插入排序算法，并对三种插入排序算法进行了详细的分析。明确各种排序算法的适用条件，熟练掌握算法思想，针对实际问题灵活运用，有助于我们更好的完成数据处理工作。

参考文献：

[1]李晶.直接插入排序算法分析与实现[J].中国科技信息，2007（24）：347+349.

[2]刘模群.排序算法时间复杂度研究[J].软件导刊，2012，11（06）：3538.