通过学习上述两种方法可以了解排序的基本思想，也可以对任何一个无序数组作出从大到小（降序）或从小到大（升序）的排列。现在假设有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。

题目：A数组中有N个数据，按从小到大的顺序排列，输入一个数X，把X的值插入到数组A中，使得插入后的A数组仍然按从小到大排列。

那么这个问题的解决算法就是：

1）、通过比较大小找到X应插入的位置，假如应该放在第I个位置；

2）、把从I开始的（包括I）的所有数组元素依次向后移动一个位置，即A[I+1]：=A[I]；

3）、A[I]：=X；

通过上述算法可以写出插入排序算法的程序流程图，如图5所示：

开  始

读入一个数到X中；I：=1

  

A[I]>X

                                                      

N

I:= I+1

I>N--1

                 

图5  插入排序算法程序流程图

按照上述流程图写出的代码如下：

          program charu(input,output);

          var

             a:array[1..11] of integer;

             x,I,j,n:integer;

             f:Boolean;

          Begin

             {给数组赋一个已经排序好的初值,设A[1]到A[10]分别等于1到10}

For I:=1 to 10 do A[I]:=I；

Writeln(‘数组原来的排列值是：’)；

For I:=1 to 10 do write（a[I]:4）;

Writeln;

Writeln(‘输入一个整数:’);

Readln(x);

F:=false;

I：=0；N：=10；

Repeat

  I:=I+1;

  If a[I]>x then f:=ture;

 Until I>n or f=ture;

J:=n+1;

While j<>I do

   begin

A[j]:=a[j-1];

J:=j-1

                   End;

A[I]:=x;

Writeln(‘ 插入一个数后的数组排列值是:’);

For I:=1 to n+1 do

   Write(a[I]:4)

End.

注意：此排序方法要求数组一定要有足够的预留空间来容纳插入后的数据。