1.定义

      将无序序列中的各元素依次插入到已经有序的线性表中。

2.分析

      在线性表中,只包含第一个元素的子表显然是有序表。接下来从线性表的第二个元素开始直到最后一个元素,逐次将其中的每一个元素插入到前面的有序表中。一般来说,假设线性表中前j–1个元素已经有序,现在要将线性表中第j个元素插入到前面的有序子表中,插入过程如下:

      首先将第j个元素放到一个变量temp中,然后从有序子表的最后一个元素开始,往前逐个与temp比较,将大于temp的元素依次向后移动一个位置,直到遇到小于它的元素,此时就将temp插入到刚移出的空位置上。若temp的值大于等于子表的最后一个元素,则将temp直接插入到子表的第j个位置。此时,有序子表的长度就变为j了。

    当然,考虑到程序的空间成本,我们可以改进程序,以省去temp变量。

废话不多说,直接上图:

source code
running result