华为机试题68-成绩排序

描述

给定一些同学的信息（名字，成绩）序列，请你将他们的信息按照成绩从高到低或从低到高的排列,相同成绩都按先录入排列在前的规则处理。

例示：
jack      70
peter     96
Tom       70
smith     67

从高到低  成绩
peter     96
jack      70
Tom       70
smith     67

从低到高

smith     67

jack      70

Tom       70

peter     96

注：0代表从高到低，1代表从低到高

数据范围：人数：1≤n≤200 

进阶：时间复杂度：O(nlogn) ，空间复杂度：O(n)

输入描述：

第一行输入要排序的人的个数n，第二行输入一个整数表示排序的方式，之后n行分别输入他们的名字和成绩，以一个空格隔开

输出描述：

按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开

示例1

输入：

3
0
fang 90
yang 50
ning 70

输出：

fang 90
ning 70
yang 50

示例2

输入：

3
1
fang 90
yang 50
ning 70

输出：

yang 50
ning 70
fang 90

---

---

解题思路：

这道题怎么是难题，可能进阶版是难题吧，需要同时满足时间复杂度O(nlogn)和稳定的要求。

我这题用的是冒泡排序算法，时间复杂度是O（n²），不满足进阶版的要求。

根据题目要求，相同成绩得按先录入排列在前的规则处理，所以这就不能偷懒只写升序或降序其中一个函数，另一个进行反序打印，这样应该不满足要求。需要注意选用稳定的排序算法，不能选用快速排序，这个算法不稳定，虽然能够满足时间复杂度O(nlogn)的要求；选择排序算法就更不能使用了，既不满足时间复杂度要求，又是不稳定的。

代码如下：

#include 
#define    N    200
typedef struct student
{
    char name[20];
    int score;
}student;
void ascend_sort(student *p,int n)
{
    int i,j;
    student temp;
    for(i=0;ip[j+1].score)
            {
                temp=p[j];
                p[j]=p[j+1];
                p[j+1]=temp;
            }
        }
    }
}
void descend_sort(student *p,int n)
{
    int i,j;
    student temp;
    for(i=0;i

 

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/875552.html