插入排序(insertion sort)算法实现

插入排序算法的原理很简单，首先将数组的第一个数data[0]看成是有序的，然后从第二个元素开始和它前面的元素进行比较，如果从前面的某一个数大，就交换。由于前面的元素是有序的，所以就使有序元素的个数逐渐增大，直到等于n。插入排序的时间复杂度为 O(n^2)。

算法的c实现如下：

#include  < stdio.h >

void  output_array( int  data[],  int  n)

{

     int  i;

     for (i  =   0 ; i  <  n; i ++ )

        printf( " %d  " , data[i]);

    printf( " \n " );

}

void  swap( int   * a,  int   * b)

{

     int  x;

    x  =   * a;

     * a  =   * b;

     * b  =  x;

}

// 算法实现

void  insertion( int  data[],  int  b,  int  e)

{

     int  i, j;

     for (i  =  b  +   1 ; i  <=  e; i ++ )

    {

         for (j  =  i; j  >   0   &&  data[j]  >  data[j  -   1 ]; j -- )

        {

            swap( & data[j],  & data[j  -   1 ]);

        }

    }

}

int  main()

{

     int  data[]  =  { 5 ,  3 ,  1 ,  665 ,  77 ,  66 ,  44 ,  11 ,  10 ,  9 ,  8 ,  6 };

    output_array(data,  12 );

    insertion(data,  0 ,  11 );

    output_array(data,  12 );

     return   0 ;

}