P026 按分数降序排列 ★★★

03-程序设计题 软件121, 唐鼎威 793浏览

所属年份:2010.9;2012.3;
学生的记录由学号和成绩组成,N名学生的数据已放入主函数中的结构体数组s中,请编写函数fun,其功能是:按分数降序排列学生的记录,高分在前,低分在后。

#include 
#define   N   16
typedef  struct
{  char  num[10];
   int   s;
} STREC;
void  fun( STREC  a[] )
{

}

main()
{  STREC  s[N]={{"GA005",85},{"GA003",76},{"GA002",69},{"GA004",85},
		{"GA001",91},{"GA007",72},{"GA008",64},{"GA006",87},
		{"GA015",85},{"GA013",91},{"GA012",64},{"GA014",91},
		{"GA011",66},{"GA017",64},{"GA018",64},{"GA016",72}};
   int  i;FILE *out ;
   fun( s );
   printf("The data after sorted :\n");
   for(i=0;i<N; i++)
   {  if( (i)%4==0 )printf("\n");
      printf("%s  %4d  ",s[i].num,s[i].s);
   }
   printf("\n");
   out = fopen("out.dat","w") ;
   for(i=0;i<N; i++)
   {  if( (i)%4==0 && i) fprintf(out, "\n");
      fprintf(out, "%4d  ",s[i].s);
   }
   fprintf(out,"\n");
   fclose(out) ;
}

【考点分析】
本题考查:排序算法;结构体类型。

【解题思路】
对N个数进行排序的算法很多,其中最简单的排序算法是冒泡算法。利用双层for循环嵌套和一个if判断语句来实现,外层循环用来控制需比较的轮数,内层循环用来控制两两比较。

【解题宝典】
冒泡法算法思路:如果有N个数,则要进行N-1次比较,在每一次比较中要进行N-1次两两比较(这种算法较好理解但不是最好的)。所谓两两比较就是从头到尾依次将相邻两个数进行比较,并将其中较大的数放在前或在后(若要求从小到大排序,则大的数要放在后面,反之对调),即两两比较后这两个数要形成题中所要求的顺序。由于总是从头到尾进行比较,第1轮比较结束后,最大(或最小)数肯定在最后,第2轮比较结束后,次最大(或次最小)数肯定在倒数第2个,依次类推,所以进行第1轮比较时必须比较到最后一个数,而进行第2轮比较时只要比较到倒数第2个数,进行第i轮比较时只需比较到第N-i-1个数即可(这种算法较难理解,但它是最好的)。
选择法算法思路:如果有N个数,则从头到倒数的第2个数逐个向后移动,每移动1个数总是对其后面的所有数进行搜索,并找出它们的最大(或最小)数,然后与该数进行比较,若大于(或小于)该数则进行交换,交换后再移动到下一个数,依次交换到结束。此外,选择法还可用如下思路:如果有N个数,则从头到倒数第2个数逐个移动,每移动一个数总是将这个数与其后的所有数进行两两比较,在比较时按顺序将进行比较的这两个数排序(即交换)。
插入法算法思路:先对前两个数进行排序。然后把第3个数插入到前两个数中,插入后前3个数依然有序;再把第4个数插入到前3个数中,插入后前4个数依然有序;依次插完所有的数。具体执行方式(假设从小到大排序):从第2个数开始往后逐个走动直到最后,每走到1个数总是将该数(先将其存到1个临时变量中)与前面的数进行比较(比较的顺序总是从后往前进行),在比较时只要发现该数比被比较的数小,就将被比较的数往后移1位,然后再与前1个数进行比较,直到发现该数比被比较的数大或已比较到头(即第1个数的前面),并将该数存入当前被比较数的后1位(存储空间)。
例如,整型一维数组a中有N个元素,要求将其按从小到大排序。注意元素下标是从0开始的。
冒泡法:

for(i=1;i<N;i++)
  for(j=0;j<N-1;j++)      if(a[j]>a[j+1]) 
      {t=a[j];a[j]=a[j+1];a[j+1]=t;}

选择法:

for(i=0;i<N-1;i++)
{
   p=i;
   for(j=i+1;j<N;j++)       if(a[p]>a[j]) p=j;
   if(p!=i)
      {t=a[i];a[i]=a[p];a[p]=t;}
}

插入法:

for(i=1;i<N;i++) {    t=a[i];    for(j=i-1;a[j]>t&&j>=0;j--)
     a[j+1]=a[j];
   a[j+1]=t;
}

【参考答案】

void  fun( STREC  a[] )
{
  int i,j;
  STREC t;
  for(i=1;i<N;i++)             /*用冒泡法进行排序,进行N-1次比较*/
     for(j=0;j<N-1;j++)        /*在每一次比较中要进行N-1次两两比较*/
       if(a[j].s<a[j+1].s)
          {t=a[j];a[j]=a[j+1];a[j+1]=t;} /*按分数的高低排列学生的记录,高分在前*/
}