例2.1 排序
时间限制：1s 内存限制：32M
题目描述：
对输入的n个数进行排序并输出。
输入：
输入的第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出：
可能有多组测试数据，对每组测试数据，将排序后的n个整数输出，每个数后面都有一个空格。每组测试数据的结果占一行。
样例输入：
4
1 4 3 2
样例输出：
1 2 3 4
来源：
2006年华中科技大学计算机保研机试真题
分析
时间限制1s，即算法复杂度不能超过一千万，1<=n<=100， n^2数量级仅在万级别，可用冒泡排序。
代码2.1 冒泡排序
//冒泡排序
#include <stdio.h>
int main()
{
int n;
int buf[100];
while(scanf("%d",&n) != EOF) //输入个数n，可能有多组数据
{
for(int i = 0; i < n; i++) //依次输入一组数据的n个数到buf中
{
scanf("%d",&buf[i]);
}
for(int i = 0; i < n-1; i++)
{
for(int j = n-1; j > i; j--)
{
if(buf[j-1] > buf[j])
{
int temp = buf[j];
buf[j] = buf[j-1];
buf[j-1] = temp;
}
}
} //冒泡排序
for(int i = 0; i < n; i++ )
{
printf("%d ", buf[i]); //依次输出，注意格式，每个数字后加空格
}
}
return 0;
}
拓展例2.1，若题设n最大能达到10000
此时不可用n^2复杂度的排序算法了，可采用快速排序。C++用内置sort库函数，C用qsort函数。
void qsort(void *base, size_t nelem, size_t width, cmp);
//*base为要排序的数组，nelem为数组长度，width为数组元素的大小(单位一字节)，cmp为自定义比较函数
int cmp_asc(const void*a, const void*b)
{
return *(int*)a-*(int*)b;
}; //升序
int cmp_desc(const void*a, const void*b)
{
return *(int*)b-*(int*)a;
}; //降序
代码2.2 快速排序 qsort
#include <stdio.h>
#include <stdlib.h>
int cmp_asc(const void*a, const void*b)
{
return *(int*)a-*(int*)b;
}; //升序
int cmp_desc(const void*a, const void*b)
{
return *(int*)b-*(int*)a;
}; //降序
int main()
{
int n;
int buf[10000];
while(scanf("%d",&n) != EOF) //输入个数n，可能有多组数据
{
for(int i = 0; i < n; i++) //依次输入一组数据的n个数到buf中
{
scanf("%d",&buf[i]);
}
qsort(buf,n,sizeof(buf[0]),cmp_desc); //快排降序
for(int i = 0; i < n; i++ )
{
printf("%d ", buf[i]); //依次输出，注意格式，每个数字后加空格
}
}
return 0;
}
例2.3 成绩排序
时间限制：1s 内存限制:32M
题目描述
输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩都按先录入排列在前的规则处理。
输入描述:
输入多行，先输入要排序的人的个数，然后输入排序方法0（降序）或者1（升序）再分别输入他们的名字和成绩，以一个空格隔开
输出描述:
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开
样例输入：
3
0
fang 90
yang 50
ning 70
样例输出：
fang 90
ning 70
yang 50
来源：
[牛客网] 2000年清华大学计算机研究生机试真题
代码2.3
#include <stdio.h>
#include <stdlib.h>
typedef struct Student{
char name[101];
int grade;
}Student;
int cmp_asc(const void *a, const void *b){
Student *c = (Student*)a;
Student *d = (Student*)b;
if(c->grade != d->grade)
return c->grade - d->grade;
}
int cmp_desc(const void *a, const void *b){
Student *c = (Student*)a;
Student *d = (Student*)b;
if(c->grade != d->grade)
return d->grade - c->grade;
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
int flag;
Student student[n];
scanf("%d", &flag);
for(int i = 0; i < n; i++)
scanf("%s %d",student[i].name,&student[i].grade);
if(flag)
qsort(student,n,sizeof(Student),cmp_asc);
else
qsort(student,n,sizeof(Student),cmp_desc);
for(int i = 0; i < n; i++)
printf("%s %d\n", student[i].name,student[i].grade);
}
return 0;
}
