插入排序(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 ;

}