Day1：排序

例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;
}