信息学奥赛一本通 排序算法


阅读数: 次   
字数统计: 2.2k字   |   阅读时长: 13分

选择，冒泡，插入，归并排序以及快排
后面是排序的应用

@TOC

选择排序

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
#include<iostream>
using namespace std;
int main()
{
	int a[100001];
	int x,i=0;
	while(cin>>x&&x!=0)
	{
		a[i]=x;
		i++;
	}
	for(int j=0;j<i;j++)
	{
		int min=a[j],sy=j;
		for(int k=j+1;k<i;k++)
			if(min>a[k])
				sy=k;
		if(sy!=j)
		{
			int z=a[sy];
			a[sy]=a[j];
			a[j]=z;
		}
	}
	for(int j=0;j<i;j++)
		cout<<a[j]<<" ";
	return 0;
}

冒泡排序

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
#include<iostream>
using namespace std;
int main()
{
	int a[100001];
	int x,num=0;
	while(cin>>x,x!=0)
	{
		a[num]=x;
		num++;
	}
	for(int j=0;j<num;j++)
	{
		bool sy=1;
		for(int i=0;i<num-1;i++)
		{
			if(a[i]>a[i+1])
			{
				int z=a[i];
				a[i]=a[i+1];
				a[i+1]=z;
				sy=0;
			}	
		}
		if(sy==1)
			break;
	}
	
	for(int j=0;j<num;j++)
		cout<<a[j]<<" ";
	return 0;
}

插入排序

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
#include<iostream>

using namespace std;
int main()
{
	int a[1000];
	int x,k=0,i,j;
	while(cin>>x,x!=0)
	{
		a[k]=x;
		k++;
	} 
	for(i=1;i<k;i++)
	{
		for(j=i-1;j>=0;j--)
		{
			if(a[j]<=a[i])
				break;
		}
		j++;
		int val=a[i];
		for(int m=i;m>j;m--)
		{
			a[m]=a[m-1];
		}
		a[j]=val;
	}
	for(int m=0;m<k;m++)
	{
		cout<<a[m]<<" ";
	}
	return 0;
}

快速排序

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
#include<iostream>
using namespace std;

void qsort(int l,int r,int a[])
{
	int i=l,j=r;
	int mid=a[(l+r)/2];
	do
	{
		while(a[i]<mid)i++;
		while(a[j]>mid)j--;
		if(i<=j)
		{
			swap(a[i],a[j]);
			i++;j--;
		}
	}while(i<=j);
	if(l<j)qsort(l,j,a);
	if(r>i)qsort(i,r,a);
}

int main()
{
	int a[10000]={1,4,5,6,8,9,0,5,3,2,2,12,4,36,45,42,5};
	qsort(0,16,a);
	for(int i=0;i<17;i++)cout<<a[i]<<" ";
	return 0;
}

归并排序

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
#include<iostream>
using namespace std;

void msort(int l,int r,int a[])
{
	if(l==r)return;
	int mid=(l+r)/2,i=l,j=mid+1,m[1000]={0},s=l;
	msort(l,mid,a);
	msort(mid+1,r,a);
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			m[s]=a[i];
			s++;i++;
		}
		else
		{
			m[s]=a[j];
			s++;j++;
		}
	} 
	while(i<=mid)
	{
		m[s]=a[i];
		s++;i++;
	}
	while(j<=r)
	{
		m[s]=a[j];
		s++;j++;
	}
	for(int k=l;k<=r;k++)
	{
		a[k]=m[k];
	}
}

int main()
{
	int a[10000]={1,4,5,6,8,9,0,5,3,2,2,12,4,36,45,42,5};
	msort(0,16,a);
	for(int i=0;i<17;i++)cout<<a[i]<<" ";
	return 0;
}

求逆序对

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
#include<iostream>
#include<cstring> 
using namespace std;

int a[100001],k[100001];
long long ans=0;

void msort(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)/2;int i=l,j=mid+1,kk=l;
	msort(l,mid);
	msort(mid+1,r);
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			k[kk]=a[i];i++;kk++;
		}	
		else
		{
			k[kk]=a[j];j++;kk++;
			ans+=mid-i+1; 
		}
	}
	while(i<=mid)
	{
		k[kk]=a[i];kk++;i++;
	}
	while(j<=r)
	{
		k[kk]=a[j];kk++;j++;
	}
	for(int p=l;p<=r;p++)
		a[p]=k[p];
}

int main()
{
	int n;
	cin>>n;
	memset(a,0,sizeof(a));
	memset(k,0,sizeof(k));
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		a[i+1]=x;
	}
	msort(1,n);
	cout<<ans;
	return 0;
}

谁考了第k名

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
#include<iostream>
#include<algorithm>
using namespace std;

class stu
{
	public:
		string s;
		float score;
};

bool cmp(stu a,stu b)
{
	return a.score>b.score;
}

int main()
{
	int n,k;
	cin>>n>>k;
	stu a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i].s>>a[i].score;
	}
	sort(a,a+n,cmp);
	cout<<a[k-1].s<<" "<<a[k-1].score;
	return 0;
}

奇数单增序列

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n];
	memset(a,0,sizeof(a));
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if(x%2==1)
			a[i]=x;
	}
	sort(a,a+n);
	int i=0;
	while(a[i]==0)i++;
	if(i<n)
		cout<<a[i];i++; 
	for(;i<n;i++)
		cout<<","<<a[i];
	return 0;
}

成绩排序

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

class stu{
	public:
		string name;
		int score;
};

bool cmp(stu a,stu b)
{
	if(a.score==b.score)return a.name<b.name; 
	return a.score>b.score;
}

int main()
{
	int n;
	cin>>n;
	stu a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i].name>>a[i].score;
	}
	sort(a,a+n,cmp); 
	for(int i=0;i<n;i++)
	{
		cout<<a[i].name<<" "<<a[i].score<<endl;
	}
	return 0;
}

奖学金

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

class stu{
	public:
		int xuehao;
		int chinese;
		int math;
		int english;
		int sum;
};

bool cmp(stu a,stu b)
{
	if(a.sum==b.sum)
	{
		if(a.chinese==b.chinese)
		{
			return a.xuehao<b.xuehao;
		}
		return a.chinese>b.chinese;
	}
	return a.sum>b.sum;
}

int main()
{
	int n;
	cin>>n;
	stu a[n];
	for(int i=0;i<n;i++)
	{
		a[i].xuehao=i+1;
		cin>>a[i].chinese>>a[i].math>>a[i].english;
		a[i].sum=a[i].chinese+a[i].math+a[i].english;
	}
	sort(a,a+n,cmp);
	for(int i=0;i<5;i++)
	{
		cout<<a[i].xuehao<<" "<<a[i].sum<<endl;
	}
	return 0;
}

分数线划定

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

class stu{
	public:
		int num;
		int s;
};

bool cmp(stu a,stu b)
{
	if(a.s==b.s)
		return a.num<b.num;
	return a.s>b.s;
}

int main()
{
	int n,m;
	cin>>n>>m;
	stu a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i].num>>a[i].s;
	}
	sort(a,a+n,cmp);
	int ss=a[m*3/2-1].s;
	int i=0;
	while(a[i].s>=ss)
	{
		i++;
	} 
	cout<<ss<<" "<<i<<endl;
	for(int j=0;j<i;j++)
		cout<<a[j].num<<" "<<a[j].s<<endl;
	return 0;
}

整数奇偶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; 
bool cmp(int a,int b){
	if(a%2!=b%2)return a%2>b%2;
	if(a%2)return a>b;
	else return a<b;
}
int main(){
	int k=10,a[10];
	for(int i=0;i<k;i++)
		cin>>a[i];
	sort(a,a+k,cmp);
	for(int i=0;i<k;i++)cout<<a[i]<<" ";
	return 0;
}

合影效果

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio> 
using namespace std;

class stu{
	public:
		bool sex;
		float s;
}; 

bool cmp(stu a,stu b)
{
	if(a.sex!=b.sex)return a.sex>b.sex;
	if(a.sex)return a.s<b.s;
	else return a.s>b.s;
}

int main(){
	int n;
	cin>>n;
	stu a[n];
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		if(s=="male")a[i].sex=1;
		else a[i].sex=0;
		cin>>a[i].s;
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++)printf("%.2f ",a[i].s);
	return 0;
}

病人排队

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

class patient{
	public:
		int num; 
		string s;
		int age;
};

bool cmp(patient a,patient b){
	if((a.age>=60)==(b.age>=60))
	{
		if(a.age>=60)
		{
			if(a.age==b.age)return a.num<b.num;
			return a.age>b.age;
		}
		return a.num<b.num;
	}
	else return a.age>b.age;
	
}

int main(){
	int n;
	cin>>n;
	patient a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i].s>>a[i].age;
		a[i].num=i;
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++)
	{
		cout<<a[i].s<<endl;
	}
	return 0;
}

明明的随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int n,k=0;
	cin>>n;int a[1001]={0};
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if(a[x]==0)k++;
		a[x]++;
	}
	cout<<k<<endl;
	for(int i=1;i<1000;i++)
	{
		if(a[i]>0)cout<<i<<" ";
	}
	return 0;
}

单词排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
using namespace std;
string a[1001];
int main()
{
    int i=0;
    while(cin>>a[i])
    {
        i++;
    }
    sort(a,a+i);
    for(int j=0;j<i+1;j++)
    {
        if(a[j]==a[j+1])
        continue;
        cout<<a[j]<<endl;
    }
    return 0;
}

出现次数超过一半的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a[101]={0},n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		a[x+50]++;
	}
	for(int i=0;i<100;i++)
	{
		if(a[i]>n/2)
		{
			cout<<(i-50);
			return 0;
		}
	}
	cout<<"no";
	return 0;
 }

统计字符数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int a[200]={0}; 
	for(int i=0;i<s.length();i++)
	{
		a[s[i]]++;
	}
	int max=0,k;
	for(int i=0;i<200;i++)
	{
		if(max<a[i]){
			max=a[i];
			k=i;
		}
	}
	cout<<char(k)<<" "<<max;
	return 0;
}


-------------本文结束感谢您的阅读-------------



赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人次

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

朱登榜，来自河南郑州，河南大学学生，倘若文章有错误，望提醒修正，感谢！<br>qq:879322660<br>微信:z15981855791