C语言实现插入排序

问题描述：

    排序问题：

    输入：N个数的一个序列<a1,a2,a3,...,an>。

    输出：输入序列的一个序列<a1',a2',a3',...,an'>,满足a1'<=a2'<=a3'<=...<=an'。

虽然排序的是一个序列，但实际上来说，输入的是有N个元素的数组。所以每一个被排序的数在排序过程中被称为关键字key。

插入排序的过程：

遍历数组中的每个关键字key，将它的位置空出来，然后从key开始往前遍历，直到找到找排在他前面的比它小的value，key之前value之后的这一段序列后移，然后将key插入到value后面，这就完成了一次插入。

具体实现：

时间复杂度分析：

行号         算法语句                       执行次数          代价 c_i

1          int i,j,key;                              1                           

2          for (j=1;j<=length;j++)            n+1                      

3          key=array[j];                           n                         

4          i=j-1;                                       n                         

5          while(i>=0&&array[i]>key)                                      

6          array[i+1]=array[i];                                         

7          i=i-1;                                                              

8          array[i+1]=key;                               n                                  

9          return array;                                     1                                 

则其时间复杂度为：

将上面的式子合并相同的项，得到：

可以看到，第 2 至第 4 项的系数以及第八项都是 n，因此可以将它们合并为 4cn 的形式，其中 ，即：

在插入排序算法的最坏情况下，数组的元素按照降序排列，即每个元素都要移动到它应该插入的位置，因此第 j 个元素需要移动 j-1 次，因此：

将  代入 ，得到：

因此，在最坏情况下，可以转化为 。将其代入原式，得到：

因此，在最坏情况下，该插入排序算法的时间复杂度仍然是 ，其中 为数组长度。

输出非增序列：

要输出非增序列，需要对插入排序算法做一些修改。在原始算法中，每次将一个元素插入已排序序列中的适当位置，这样可以得到递增的序列。为了得到非增序列，需要修改插入操作的逻辑，即如果插入的元素小于或等于已排序序列中的某个元素，则将其插入到该元素的后面，否则插入到序列的最前面。

本文给出示例代码如下：

至此，插入排序完毕。