排序类问题
标签: 机试攻略 - 高分篇
学习人数: 30.7k


高清播放
赞赏支持

排序类的问题基本上是每个学校必考的知识点,所以它的重要性不言而喻。
如果你在网上一查,或者看数据结构书,十几种排序算法可以把你吓的魂不守舍。表面上看各种排序都有其各自的特点,那是不是我们需要掌握每一种排序呢?
答案自然是否定的。我们一种排序也不需要掌握,你需要会用一个sort函数就可以了,正所谓一个sort走天下。

 

sort函数本质上是封装了快速排序,但是它做了一些优化,所以你只管用它就行了。
复杂度为:nlogn
所以sort可以对最大30W个左右的元素进行排序,可以应对考研机试中的99.9%的情况。

 

sort函数的用法

sort()函数:依次传入三个参数,要排序区间的起点,要排序区间的终点+1,比较函数。比较函数可以不填,则默认为从小到大排序。

 

sort函数有两个常见的应用场景

1、自定义函数排序
2、多级排序

 

成绩排序
题目描述:
输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩都按先录入排列在前的规则处理。
示例:
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(升序)再分别输入他们的名字和成绩,以一个空格隔开
输出描述:
按照指定方式输出名字和成绩,名字和成绩之间以一个空格隔开
输入样例#:
3
0
fang 90
yang 50
ning 70
输出样例#:
fang 90
ning 70
yang 50
题目来源:
DreamJudge 1151

题目解析:这题唯一的一个考点在于稳定排序,sort排序是不稳定的,排序之后相对次序有可能发生改变。解决这个问题有两个方法,一个是用stable_sort函数,它的用法和sort一样,但是它是稳定的,所以如果我们遇到有稳定的需求的排序时,可以用它。另一个方法是给每一个输入增加一个递增的下标,然后二级排序,当值相同时,下标小的排在前面。

 

参考代码(稳定排序)

#include <bits/stdc++.h>  
using namespace std;  
  
struct Student {  
    string name;  
    int grade;  
}stu[1005];  
//从大到小排序  
bool compareDesc(Student a,Student b) {  
    return a.grade > b.grade;  
}  
//从小到大排序  
boo...
登录查看完整内容


课后作业

练习题目

DreamJudge 1106 排序2
DreamJudge 1159 成绩排序2.0
DreamJudge 1217 国名排序
DreamJudge 1227 日志排序
DreamJudge 1248 整数奇偶排序
DreamJudge 1254 字符串排序
DreamJudge 1255 字符串排序2
DreamJudge 1261 字符串排序3
DreamJudge 1294 后缀子串排序
DreamJudge 1310 奥运排序问题
DreamJudge 1338 EXCEL排序
DreamJudge 1360 字符串内排序
DreamJudge 1399 排序 - 华科
DreamJudge 1400 特殊排序
DreamJudge 1404 成绩排序 - 华科
DreamJudge 1412 大整数排序


登录后开始许愿

暂无评论,来抢沙发