STL模板之vector与sort的使用
STL模板之vector与sort的使用
@(算法学习)
题目描述
题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩.都按先录入排列在前的规则处理。
例示：
jack 70
peter 96
Tom 70
smith 67
从高到低 成绩
peter 96
jack 70
Tom 70
smith 67
从低到高 成绩
smith 67
Tom 70
jack 70
peter 96
输入描述
输入多行，先输入要排序的人的个数，然后输入排序方法0（降序）或者1（升序）再分别输入他们的名字和成绩，以一个空格隔开
###输出描述:###
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开。
输入例子:
3
0
fang 90
yang 50
ning 70
输出例子:
fang 90
ning 70
yang 50
参考解法：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct node
{
string name;
int grade;
int seq;
} student;
int bit = 0; //0:降序输出； 1：升序输出
bool compare(student a, student b)
{
if(bit == 1)
{
if(a.grade == b.grade)
{
return a.seq < b.seq;
}
else
{
return a.grade < b.grade;
}
}
else // bit == 0时
{
if(a.grade == b.grade)
{
return a.seq < b.seq;
}
else
{
return a.grade > b.grade;
}
}
}
int main()
{
int n;
while(cin >> n >> bit)
{
vector<student> students;
for(int i = 0; i < n; i++)
{
student stu;
stu.seq = i;
cin >> stu.name >> stu.grade;
students.push_back(stu);
}
//按照成绩排序--升序
sort(students.begin(),students.end(),compare);
for(auto it = students.begin(); it != students.end(); it++)
{
cout << (*it).name << " " << (*it).grade << endl;
}
}
return 0;
}
分析：基于C++的STL模板，则最关键的排序算法就不用自己动手写了。什么快排，堆排等等都作为基础掌握就好，这里主要强调直接运用STL的sort函数直接帮我们排好序。
针对一般的vector<int>ins数组，如果只是存的数字元素，直接sort(ins.begin(),ins.end()),默认是递增排序。
如果vector存的是自定义的结构体，同样可以用sort，但是排序规则就需要自己定义了。只用在sort函数后面加上自定义的比较函数名字，注意不是函数调用，而是函数名字。即函数作为参数，被调用的是外层函数。
这题的具体思路就是定义一个结构体存储学生的姓名和成绩。定义一个序号seq是为了跟踪输入的次序，也作为排序的一个参数。
所以，整个逻辑非常清楚，就是处理好输入数据，调用sort，输出即可。
啰嗦一句，在C中可用：
while(scanf("%d",&a)!=EOF)
{
...
}
来进行多个case的处理。
在C++的语法下，上面的也可以用，但是如果用cin流处理，则:
while(cin >> a)
{
...
}
都表示输入流非空。很小也很基础的细节。
关于比较函数，是布尔型，如果返回的是false，表示递增，返回true表示递减。
即左项减右项。
2019.10 Update:
END.