csort.c

该内容是《》一书的光盘内容

  {
	/* 所有排序算法 */
   case all    :
	/* 冒泡排序 */
   case bubble :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + bubble) );
            Bubble( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* 延迟交换排序 */
   case delayed:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + delayed) );
            Delayed( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* 希尔排序 */
   case shell  :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + shell ));
            Shell( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* Metzner希尔排序 */
   case shell_metzner:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + shell_metzner) );
            Shell_Metzner( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* 快速排序 */
   case quick  :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + quick) );
            Quicksort( array, 0, elements - 1, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* 插入排序 */
   case insertion:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + insertion) );
            Insertion( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );
	/* 停止 */
   case stop:

   default:;
  }
}


/*****  initialize函数  *********************************/
/*							                            */
/*  初始化图形驱动									    */
/*														*/
/********************************************************/

void Initialize( void )
{
 int    GraphDriver; /* 图形设备驱动   */
 int    GraphMode;   /* 图形模式值      */
 int    ErrorCode;   /* 出错代码  */

 GraphDriver = DETECT;              /* 自动检测显示设备类型 */
 initgraph( &GraphDriver, &GraphMode, "" );
 ErrorCode = graphresult();   /* 读取初始化的结果*/
 if( ErrorCode != grOk )      /* 如果在初始化的过程中发生错误  */
   {
    printf(" Graphics System Error: %s\n", grapherrormsg( ErrorCode ) );
    exit( 1 );
   }

}

/*****  gprintf函数  ************************************/
/*						                                */
/*  和C标志库中的PRINTF函数很类似。但是gprintf可以      */
/*  图形模式中在指定的坐标位置显示文本			        */
/*														*/
/*                                                      */
/*  gprintf函数的返回值并没有被使用						*/
/*                                                      */
/********************************************************/

int gprintf( int *xloc, int *yloc, char *fmt, ... )
{
 va_list  argptr;  /* 参数列表指针          */
 char str[80];     /* 用来保存参赛    */
 int count;        /* vspringf的放回值  */

 va_start( argptr, fmt );               /* 初始化va_ 函数         */
 count = vsprintf( str, fmt, argptr );  /* 把字符串放到存储区中	  */
 outtextxy( *xloc, *yloc, str );        /* 在图形模式下显示字符串 */
 va_end( argptr );                      /* 关闭va_ 函数			  */
 return( count );                       /* 返回显示的字符数		  */

}


/*****  Setscreen  *******************************************************

   为排序初始化屏幕

   调用者: driver

   参数:

    int *array         要排序的数组

    int elements       元素的个数

    int random         random = 1或者worst case = 0

*************************************************************************/

void Setscreen( int *array, int elements, int random )
{
int j;

cleardevice();

/* 随机产生元素系列 */
if ( random )
  {
   randomize();
   for ( j = 0; j < elements; j++ )
     {
      *( array + j) = random( elements );
      putpixel( 3*j, *(array+j), 10);
     }
  }
else /* 初始化最坏情况，即元素全部倒置 */
  {
   for ( j = 0; j < elements; j++ )
     {
      *(array + j) = elements - j;
      putpixel( 3*j, *(array+j), 10);
     }

   }
}



/*****  Swap_Pixels函数  ****************************/
/*                                                  */
/*  交换两个数组元素，并且改变相应的象素位置        */
/*  通过打开和关闭显示来制作动画效果				*/
/*                                                  */
/****************************************************/

int Swap_Pixels( int *array, int i, int j, int delay_factor )
{
int h;
h = *(array + i);
putpixel( 3 * i, *(array + i), 0);
putpixel( 3 * j, *(array + i), 10 );
*(array + i) = *(array + j);
putpixel( 3 * j, *( array + j), 0 );
putpixel( 3 * i, *(array + j), 10 );
*(array + j) = h;

delay( delay_factor );
return( h );
}

/*****  冒泡排序 ************************************/
/*                                                  */
/****************************************************/

void Bubble( int *array, int elements, int delay_factor )
{
int i,j;

for ( i = 0; i < elements - 1 ; i++ )
 for ( j = i + 1; j < elements; j++ )
   {
    if ((*(array+i)) > (*(array+j)))
      {
       Swap_Pixels( array, i, j, delay_factor );
      }
   }
}

/*****  延迟交换排序  *******************************/
/*                                                  */
/****************************************************/

void Delayed( int *array, int elements, int delay_factor )
{
int p, h, k, i, j;

for ( p = 0; p < elements-1; p++ )
 {
  h = p;
  for ( k = p + 1; k < elements ; k++ )
    if (*(array+k) < *(array+h))
      h = k;
  if ( p != h )
   {
    i = h;
    j = p;
    Swap_Pixels( array, i, j, delay_factor );
   }
 }
}

/*****  希尔排序  ***********************************/
/*                                                  */
/****************************************************/

void Shell( int *array, int elements, int delay_factor )
{
 int p, f, i, j, m;


p = elements;
while ( p > 1)
  {
   p /= 2;
   
   m = elements - p;
   do{
     f = 0;
     for ( j = 0; j < m; j++ )
       {
        i = j + p;
        if (*(array + j) > *(array + i))
          {
           Swap_Pixels( array, i, j, delay_factor );
           f = 1;
          }
       }
     } while( f );
  }
}

/*****  Metzner希尔排序  ****************************/
/*                                                  */
/****************************************************/

void Shell_Metzner( int *array, int elements, int delay_factor )
{
int p, k, t, i, j;

p = elements;
p /= 2;
while ( p != 0 )
  {
  k = elements - p;
  for ( t = 0; t < k; t++ )
    {
    i = t;
    while ( i >= 0 )
      {
      j = i + p;
      if (*(array+j) < *(array + i))
        {
        Swap_Pixels( array, i, j, delay_factor );
        i = i - p;
        }
      else
        break;
      }
    }
  p /= 2;
  }
}

/*****  快速排序  ***********************************/
/*                                                  */
/****************************************************/

void Quicksort( int *array, int left, int right, int delay_factor )
{
 int i, j, t;

 if ( right > left )
 {
  i = left - 1; j = right;
  do {
      do i++;
        while ( array[i] < array[right] );
      do j--;
        while ( array[j] > array[right] && j > 0 );
      t = Swap_Pixels( array, i, j, delay_factor );
     } while ( j > i );

      putpixel( 3*j, *(array + j), 0);
      array[j] =array[i];
      putpixel( 3*j, *(array + j), 10 );
      putpixel( 3*i, *(array + i), 0 );
      array[i] =array[right];
      putpixel( 3*i, *(array + i), 10 );
      putpixel( 3*right, *(array + right), 0 );
      array[right] = t;
      putpixel( 3*right, *(array + right), 10 );

      Quicksort( array, left, i - 1, delay_factor );
      Quicksort( array, i + 1, right, delay_factor );

  }
}


/*****  插入排序  ***********************************/
/*                                                  */
/****************************************************/

void Insertion( int *array, int elements, int delay_factor )
{
 int p, j, t;


 for ( p = 0; p < elements - 1; p++ )
   {
    t = *(array + p + 1);
    for ( j = p; j >= 0; j-- )
      {
       if ( t <= *(array + j) )
         {
          *(array + j + 1) = *(array + j);
          putpixel( 3*(j + 1), *(array + j + 1), 10 );
          putpixel( 3*j, *(array + j + 1), 0 );
          delay( delay_factor );
         }
       else
         break;
      }
    *(array + j + 1) = t;
    putpixel( 3*(p + 1), t, 0 );
    putpixel( 3*(j + 1), t, 10 );
   }
}