实验报告题目及要求 一、实验题目 设某班级有6名同学，本学期开设3门课程。现已给出奇偶交换排序算法实现

Question

实验报告题目及要求

一、实验题目
设某班级有6名同学，本学期开设3门课程。现已给出奇偶交换排序算法实现如下功能：（C程序算法Scoremain.c）
1．输入每个学生的学号、姓名和三门课程的成绩;
2．计算每个学生本学期的总分；
3．把学生成绩按总分升序排列名次（总分相同者为同名次），并按名次列出学生的学号，姓名和各科成绩；
4．升序列出每门课程成绩排在前3名的学生的学号、姓名和成绩。
二、实验要求和内容
1．修改算法。对实现上述功能的排序算法分别改用冒泡排序、简单选择排序和直接插入排序来实现；
2．将四种升排序算法（奇偶交换排序、冒泡排序、简单选择排序和直接插入排序）修改为降序算法；
3．编译、链接以上算法，按要求写出实验报告，并将修改后算法的所有语句加下划线，没做修改语句保持按原样不动。实验报告内容如下：
（1） 实验题目；
（2） 实验要求和内容；
（3） 实验环境；
（4） 实验过程（四种排序算法修改后的全部清单）；
（5） 实验结果（四种排序算法模拟运行后的实验结果）；
（6） 实验体会。
4．用A4纸打印输出实验报告。
三、实验说明
1．实验数据可自定义（数据类型见算法定义），但每种排序算法数据要求均不重复；
2．实验数据均采用中文输入方式。
#include "stdio.h"
#include "string.h"
#define M 6
#define N 3
struct student
{ char name[10];
int number;
int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/
}stu[M];
void changesort(struct student a[],int n,int j)
{int flag=1,i;
struct student temp;
while(flag)
{ flag=0;
for(i=1;i<n-1;i+=2) /*对所有奇数项进行一遍比较*/
if (a[i].score[j]>a[i+1].score[j])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
flag=1;
}
for(i=0;i<n-1;i+=2) /*对所有偶数项进行一遍比较*/
if (a[i].score[j]>a[i+1].score[j])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
flag=1;
}
}
}

Answer 1

只用快排就可以了，，没必要用到哪些插入或者冒泡，效率太低了！！！！！！

在c++中qsort()排序函数的使用qsort函数应用大全
七种qsort排序方法
<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *B)
{
return (*(In *)a)->data > (*(In *)B)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct In
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)B)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、计算几何中求凸包的cmp
int cmp(const void *a,const void *B) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) // 如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}
:
c++中加载头文件 "iostream"
c中qsort函数包含在<stdlib.h>的头文件里，strcmp包含在<string.h>的头文件里

/*六类qsort排序方法

P.S.:qsort函数是ANSI C标准中提供的，其声明在stdlib.h文件中，是根据二分发写的，其时间复杂度为n*log(n),其结构为：

void qsort(void *base,size_t nelem,size_t width,int (*Comp)(const void *,const void *));

其中：

*base 为要排序的数组

nelem 为要排序的数组的长度

width 为数组元素的大小（一字结为单位）

（* Comp）(const void *p1,const void *p2) 为判断大小函数的指针，这个函数需要自己定义，如果p1>p2,函数返回-1；a<b,函数返回1；a==b函数返回0。

前一段时间做题觉得qsort函数很好用，但有时不太会用比如按结构体一级排序、二级排序、字符串排序等，故通过查资料将其整理一番。

以下是其具体分类及用法(若无具体说明是以升序排列)：

例子1：对一维数组进行排序

#include <stdio.h>
#include <stdlib.h>
int Comp(const void *p1,const void *p2 )

{

return *((int *)p1) - *((int *)p2);

}

int main()

{
int list[100];

for(int i=0;i<10;i++)
scanf("%d",&list[i]);
qsort(list, 10,sizeof(int),Comp);
for(int i=0;i<10;i++)
printf("%d ",list[i]);
system("pause");
return 0;

}

例子2：对字符串进行排序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int Comp(const void *p1,const void *p2)

{

return strcmp((char *)p1,(char *)p2);

}

int main()

{
char a[100][100];
for(int i=0;i<3;i++)
gets(a[i]);
qsort(a,3,sizeof(a[0]),Comp);
for(int i=0;i<3;i++)
puts(a[i]);
system("pause");
return 0;

}

例子3：按结构体中某个关键字排序（对结构体一级排序）：
#include <stdio.h>
#include <stdlib.h>
struct ab
{
int vote1;
int id;
}abc[6];

int cmp(const void *a, const void *b)
{
return ((struct ab *)a)->vote1-((struct ab *)b)->vote1;
}

int main()
{
for(int i = 0; i < 5; i++)
scanf("%d",&abc[i].vote1);
qsort((void *)abc,5,sizeof(abc[0]),cmp);
for(int i=0;i<5;i++)
printf("%d ",abc[i]);

system("pause");
return 0;
}

例子4：按结构体中多个关键字排序（对结构体多级排序）[以二级为例]：

#include <stdio.h>
#include <stdlib.h>

struct ab
{
int x;
int y;
}abc[6];

int cmp(const void *a, const void *b)
{
if(((struct ab *)a)->x!=((struct ab *)b)->x)
return ((struct ab *)a)->x-((struct ab *)b)->x;
else
return ((struct ab *)a)->y-((struct ab *)b)->y;
}

int main()
{
for(int i = 0; i < 5; i++)
{
scanf("%d%d",&abc[i].x,&abc[i].y);
}
qsort((void *)abc,5,sizeof(abc[0]),cmp);
for(int i=0;i<5;i++)
printf("%d %d ",abc[i].x,abc[i].y);

system("pause");
return 0;
}

例子 5：对结构体中字符串进行排序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ab
{
int x;
char ac[100];
}abc[6];

int cmp(const void *a, const void *b)
{
return strcmp(((struct ab *)a)->ac,((struct ab *)b)->ac);
}

int main()
{
for(int i = 0; i < 5; i++)
{
gets(abc[i].ac);
}
qsort((void *)abc,5,sizeof(abc[0]),cmp);
for(int i=0;i<5;i++)
puts(abc[i].ac);

system("pause");
return 0;
}

6、计算几何中求凸包的Comp

//以下是俺从别人那儿抄来的，暂时还没用过

int Comp(const void *p1,const void *p2)

//重点Comp函数，把除了1点外的所有的点旋转角度排序

{

struct point *c=(point *)p1;

struct point *d=(point *)p2;

if( cacl(*c, *d,p[1]) < 0) return 1;

else if(!cacl(*c, *d, p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y ) )

//如果在一条直线上，则把远的放在前面

return 1;

else return -1;

}

再次P.S.:qsort函数是ANSI C标准中提供的，其声明在stdlib.h文件中，是根据二分发写的，其时间复杂度为n*log(n),其结构为：

void qsort(void *base,size_t nelem,size_t width,int (*Comp)(const void *,const void *));

其中：

*base 为要排序的数组

nelem 为要排序的数组的长度

width 为数组元素的大小（一字结为单位）

（* Comp）(const void *p1,const void *p2) 为判断大小函数的指针，这个函数需要自己定义，如果p1>p2,函数返回-1；a<b,函数返回1；a==b函数返回0。

//////////////
又见qsort--------zju2727
一道按给定关键字三级排序题，直接套入曾总结过的qsort模型就AC了。算是上次总结的一个补充实例吧。
源代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node{
char Name[100];
int Year,Price;
}Book[100];
/*----------------------------------------------------------------------------*/
/*int CompY(const void *p1,const void *p2)//首先按year排序
{
struct Node *c = (Node *)p1;
struct Node *d = (Node *)p2;
if(c->Year != d->Year) return c->Year-d->Year;
else if(strcmp((*(Node *)p1).Name,(*(Node *)p2).Name))
return strcmp((*(Node *)p1).Name,(*(Node *)p2).Name);
else return c->Price-d->Price;
}

int CompP(const void *p1,const void *p2)//首先按price排序
{
struct Node *c = (Node *)p1;
struct Node *d = (Node *)p2;
if(c->Price != d->Price) return c->Price-d->Price;
else if(strcmp((*(Node *)p1).Name,(*(Node *)p2).Name))
return strcmp((*(Node *)p1).Name,(*(Node *)p2).Name);
else return c->Year-d->Year;
}

int CompN(const void *p1,const void *p2)//首先按name排序
{
struct Node *c = (Node *)p1;
struct Node *d = (Node *)p2;
if(strcmp((*(Node *)p1).Name,(*(Node *)p2).Name))
return strcmp((*(Node *)p1).Name,(*(Node *)p2).Name);
else if(c->Year != d->Year) return c->Year-d->Year;
else return c->Price-d->Price;
}
/*-------------------------------------------------------------------*/
/*void outres(int n)
{
int i;
for(i=0;i<n;i++)
printf("%s %d %d\n",Book[i].Name,Book[i].Year,Book[i].Price);
}
/*-----------------------------------------------------------------*/
/*int main()
{
int n;
char format[15];
//freopen("in.txt","r",stdin);
scanf("%d",&n);
while(n)
{
for(int i=0;i<n;i++)
scanf("%s%d%d",Book[i].Name,&Book[i].Year,&Book[i].Price);
scanf("%s",format);
if(format[0]=='Y')
{
qsort(Book, n, sizeof(Book[0]), CompY);
}
else if(format[0]=='P')
{
qsort(Book, n, sizeof(Book[0]), CompP);
}
else
{
qsort(Book, n, sizeof(Book[0]), CompN);
}

outres(n);
scanf("%d",&n);
if(n)printf("\n");
}
return 0;
}

*/

poj3664

#include <stdio.h>
#include <stdlib.h>
struct ab
{
int vote1;
int vote2;
int id;
}abc[1000000];

int cmp1(const void *a, const void *b)
{
return ((struct ab *)a)->vote1-((struct ab *)b)->vote1;
}
int cmp2(const void *a,const void *b)
{
return ((struct ab *)a)->vote2-((struct ab *)b)->vote2;
}

int main()
{
int i,j,k;
scanf("%d%d",&j,&k);
for(i = 0; i < j; i++)
{
scanf("%d%d",&abc[i].vote1, &abc[i].vote2);
abc[i].id = i + 1;
}
qsort((void *)abc,j,sizeof(abc[0]),cmp1);
qsort((void *)(&abc[j-k]),k,sizeof(abc[0]),cmp2);
printf("%d\n",abc[j-1].id);

//system("pause");
return 0;
}