Level3题解（1-10）

  2. 主页
  4. 文档
  6. Level3题解（1-10）
  8. 第2课 数据排序1
  10. sort函数

sort函数

sort()函数是C++提供的一种排序方法之一，它使用的排序方法是类似于快排的方法（既有快速排序又有与其它排序方法的结合），时间复杂度为  ，执行效率很高！sort函数包含在头文件为<algorithm> 。sort()函数为非稳定排序，稳定排序可以用stable_sort()函数。

sort函数使用模板

#include <algorithm>
sort(start, end, 排序方法)

sort函数有三个参数：

  • 第一个是要排序的起始地址。
  • 第二个是要排序的结束地址。
  • 第三个参数是排序的方法，默认的排序方法是从小到大排序。

sort()函数的强大之处是在它的第三个参数，排序方法，就是说可以任意的设定自己的规则，使排序对象按照自己指定的规则进行排序。特别是在对字符串数组进行比较时用处很大，可以很轻松的解决一些字符串排序的算法问题。

  • 「特别强调：排序范围是[a, b), 闭区间 开区间, – 包含a 不包含b」
  • 「特别强调：C++里两个字符串字节进行比较时，是把字符串的每个字符从首端开始进行按照ASCII值的大小进行比较，如果相同，依次往下比.」

示例 从小到大排列


#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int a[7] = {123, 456, 32, 3553, 234, 342, 234};

int main()
{
	sort(a, a+7);
	for(int i=0; i < 7; i++) {
		printf("%d ", a[i]);
	}

	return 0;
 }


示例 容器

vector <int> a;sort(a.begin(), a.end());

示例 比较函数 从大到小排列

#include <cstdio>#include <iostream>#include <algorithm>
using namespace std;
int a[7] = {123, 456, 32, 3553, 234, 342, 234};
bool compare(int a, int b){    return a > b;}
int main(){	sort(a, a+7, compare);	for(int i=0; i < 7; i++) {		printf("%d ", a[i]);	}
	return 0; }

结构体比较

比较函数

struct Node {    int len;    int last;} node[100008];
bool compare(Node &n1, Node &n2){	if (n1.last == b.last)		return len > b.len;	return last < b.last;}
//应用sort(node + 1, node + 1 + n, compare);

< 重载

struct Node {	int len;	int last;
	bool operator < ( const node &b ) const {		if (last == b.last)			return len > b.len;		return last < b.last;	}};
Node node[200];sort(node+1, node+100);

P1478 陶陶摘苹果(升级版)

题目描述

又是一年秋季时，陶陶家的苹果树结了 n 个果子。陶陶又跑去摘苹果，这次他有一个 a 公分的椅子。当他手够不着时，他会站到椅子上再试试。

这次与 NOIp2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 s 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 s<0之前最多能摘到多少个苹果。

现在已知 nn 个苹果到达地上的高度 xi，椅子的高度 a，陶陶手伸直的最大长度 b，陶陶所剩的力气 s，陶陶摘一个苹果需要的力气 yi，求陶陶最多能摘到多少个苹果。

输入格式

第 1 行：两个数 苹果数 n，力气 s。

第 2 行：两个数 椅子的高度 a，陶陶手伸直的最大长度 b。

第 3 行~第 3+n-1 行：每行两个数 苹果高度 xi，摘这个苹果需要的力气 yi。

输出格式

只有一个整数，表示陶陶最多能摘到的苹果数。

输入输出样例

输入 #1复制

  • 
8 1520 130120 3150 2110 7180 150 8200 0140 3120 2
  • 输出 #1复制

4

说明/提示

对于 100% 的数据，n≤5000, a≤50, b≤200, s≤1000, xi≤280, yi≤100。

分析

结构体sort排序

struct apple{	int xi;	int yi;};
int n, s;int a, b;int cnt = 0;
struct apple apple[5005];
bool compare(struct apple a1, struct apple a2){	return(a1.yi < a2.yi);}
int main(){	int x, y, k=0;	scanf("%d %d", &n, &s);	scanf("%d %d", &a, &b);	for(int i=0; i <n; i++){		scanf("%d %d", &x, &y);		if (x > a+b)			continue;		apple[k].xi = x;		apple[k].yi = y;		k++;	}
	sort(apple, apple+k, compare);
	for(int i = 0; i < k; i++)	{		if(s >= apple[i].yi) {			s -= apple[i].yi;			cnt++;		} else			break;	}
	printf("%d", cnt);}

P1104 生日

题目描述

cjf君想调查学校OI组每个同学的生日，并按照从大到小的顺序排序。但cjf君最近作业很多，没有时间，所以请你帮她排序。

输入格式

有2行，

第1行为OI组总人数n；

第2行至第n+1行分别是每人的姓名s、出生年y、月m、日d。

输出格式

有n行，

即n个生日从大到小同学的姓名。(如果有两个同学生日相同, 输入靠后的同学先输出)

输入输出样例

  • 输入 #1
  • 
3Yangchu 1992 4 23Qiujingya 1993 10 13Luowen 1991 8 1
  • 输出 #1
  • 
LuowenYangchuQiujingya

说明/提示

数据规模

1<n<100, length(s)<20

分析

直接sort 写基于日期的比较函数.

示例代码

#include <bits/stdc++.h>using namespace std;
struct student {	int idx;	string name;	int year;	int month;	int date;};
student s[102];
bool compare(student &s1, student &s2){	if(s1.year < s2.year)		return true;	if(s1.year > s2.year)		return false;
	if(s1.month < s2.month)		return true;	if(s1.month > s2.month)		return false;
	if(s1.date < s2.date)		return true;	if(s1.date > s2.date)		return false;
	if(s1.idx > s2.idx)		return true;	else		return false;}
int main(){	int n;	cin >> n;	for(int i = 1; i <= n; i++) {		cin >> s[i].name;		cin >> s[i].year;		cin >> s[i].month;		cin >> s[i].date;		s[i].idx = i;	}
	sort(s+1, s+n+1, compare);
	for(int i = 1; i <= n; i++) {		cout << s[i].name<<endl;	}
    return 0;}

sort 虽好, 也不是万能的

sort的时间复杂度是 . 在NOIP考试中,一般数据规模在  左右时,是可以用sort进行排序的.

还记得 P1271 【深基9.例1】选举学生会 这道题目吗?  选票规模是 2000000 . 如果相对选票进行sort排序的话, 会超时的.

P1923 【深基9.例4】求第 k 小的数

题目描述

输入 n(n<5000000 且 n 为奇数) 个数字 ai (0<ai<10^9) ，输出这些数字的第 k 小的数。最小的数是第 0 小。

输入格式

无

输出格式

无

输入输出样例

  • 输入 #1
  • 
5 14 3 2 1 5
  • 输出 #1
  • 
2

sort 排序, 然后输出下标K的那个???

数据规模是 5000000, sort排序会超时.

#include<bits/stdc++.h>using namespace std;
int x[5000005],k;int main(){	int n;	scanf("%d %d",&n,&k);	for(int i=0;i<n;i++)		scanf("%d",&x[i]);	sort(x,x+n);	printf("%d",x[k]);}

sort只能得60分.

快排

手写快排且只处理可能的部分. 可能的部分就是k会出现的部分. 这样的话每次可以丢掉一部分不处理, 所以可以节省时间

参考代码:

#include<bits/stdc++.h>using namespace std;
const int MAXN = 5000005;int n, k, a[5000005];
void qsort(int s, int t){	int mid = a[(s + t)/ 2];	int lft = s, rgt = t;	if(lft >= rgt)		return;
	while(lft <= rgt) {		while(a[rgt] > mid)			rgt--;		while(a[lft] < mid)			lft++;
		if(lft <= rgt)		{			swap(a[lft], a[rgt]);			lft++;			rgt--;		}	}	if( k <= rgt) qsort(s, rgt);	else if(k >= lft) qsort(lft, t);	else {		return;	}}
int main(){	ios::sync_with_stdio(false);	cin >> n >> k;
	for(int i = 0; i < n; i++)		cin >> a[i];
	qsort(0, n-1);	cout << a[k];
	return 0;}