排序

当你看到一个杂乱的序列，你可能想让它有序。这时，你就需要排序算法为什么听着像广告词？

这有一些你不会用到的排序算法的伪代码，因为CCF可能会考。。。

、

insertion_sort.png
selection_sort.png
counting_sort.png
merge_sort.png
radix_sort.png
bubble_sort.png

heap_sort.png

sort

这东西在C++旧版的平均复杂度是O(nlogn)O(nlogn)，所以才出现了瑞士轮坑死一片的情形

现在是要求最坏时间复杂度O(nlogn)所以可以放心使用sort!!!

sort(首地址，尾地址，顺序)

下面是一个cmp的格式

1
2
3
4
bool cmp(typrename a, typename b)
{
    return //表达式,表示排序的顺序规定
}

nth_element(fir,nth,sec,cmp)

平均O(nlogn)O(nlogn)

例题P1068 NOIP2009 普及组 分数线划定

排序板子题，贴个代码

Code:

建议读者自己先Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
	Name:
	Author: xiaruize
	Date:
*/
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define form(i,j,n) for(int i=int(j);i<=int(n);i++)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define int ll

struct stu{
	int k,s;
}a[5005];

int cmp(stu a,stu b)
{
	if(a.s!=b.s)
	{
		return a.s>b.s;
	}
	else
	{
		return a.k<b.k;
	}
}
signed main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].k>>a[i].s;
	}
	sort(a,a+n,cmp);
	m=floor(m*1.5)-1;
	cout<<a[m].s<<' ';
	for(int i=0;i<n;i++)
	{
		if(a[i].s<a[m].s)
		{
			cout<<i<<endl;
			break;
		}
			
	}
	for(int i=0;i<n;i++)
	{
		if(a[i].s<a[m].s)
			break;
		else
			cout<<a[i].k<<' '<<a[i].s<<endl;
	}
	return 0;
}