排序专题

发布于 2019-01-27  312 次阅读


终于把数据排序写完了,肝了几天emmmm,首先声明一下有些题我知道可以用很简单的写法,但是写这些题本身就不是为了过题,而是为了提升码力,因为我码力太差了,所以可能写得有点复杂。
下文所有题目来自一本通OJ数据排序专题,部分贴加的来自luogu。
1.冒泡排序

#include<iostream>
const int INF =10000;
using namespace std;
int main(){
    int N,a[INF]={0},temp,tot=0;
    cin>>N;
    for(int i=1;i<=N;i++)cin>>a[i];
	for(int i=1;i<=N-1;i++)
	for(int j=1;j<=N-i;j++)
	{
		if(a[j+1]<a[j]){
			swap(a[j],a[j+1]);
		tot++;
	}
	}
    cout<<tot<<endl;
    return 0;
}

2.归并

#include<iostream>
using namespace std;
const int N =1000010;
long long  cnt=0,A[N],t[N];
void m(int l,int r){
  if(r-l>1){
  int mid=l+(r-l)/2;
  int x=l,y=mid,i=l;
  m(l,mid);
  m(mid,r);
  while(x<mid || y<r){
    if(y>=r || (x<mid && A[x]<=A[y])) t[i++]=A[x++];
    else {t[i++]=A[y++];cnt+=mid-x;}
  }
  for(int i=l;i<r;i++)A[i]=t[i];
}
}
int main(){
  int n;cin>>n;
  for(int i=1;i<=n;i++)cin>>A[i];
  m(1,n+1);
  std::cout << cnt << '\n';
  return 0;
}

3.结构体加快速选择作法 O(n)

#include<iostream>
using namespace std;
struct node{
  int xh;
  double fs;
}A[100];
int k,n,ans;
void qs(int a,int b){
  if(a>=b)
  {ans=a;return ;}
  int l=a,r=b;
  double mid=A[l].fs;
  int tempxh=A[l].xh;
  while(l<r){
    while(l<r && A[r].fs<=mid) r--;
    A[l].fs=A[r].fs;
    A[l].xh=A[r].xh;
  while(l<r && A[l].fs>=mid) l++;
    A[r].fs=A[l].fs;
    A[r].xh=A[l].xh;
  }
   A[l].xh=tempxh;
   A[l].fs=mid;
  if(l==k)ans=l;
  else if(l>k)qs(a,l-1);
  else qs(l+1,b);
}
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {std::cin >> A[i].xh>>A[i].fs;}
  qs(1,n);
  std::cout <<A[ans].xh<<" " <<A[ans].fs <<" ";
  return 0;
}

4.sort

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[500],ans[500],cnt=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]%2!=0)
		{
			ans[++cnt]=a[i];
		}
	}
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)
	{
		if(i!=cnt)
	cout<<ans[i]<<",";
	else cout<<ans[i]<<"\n";
	}
	return 0;
}

5.归并加结构题

#include<iostream>
#include<cstring>
using namespace std;
struct student{
	char name[30];
	int fs;
}A[20],temp[20];
void m(int a,int b)
{
	if(b-a>1)
	{
		int mid=a+(b-a)/2;
		int l=a,r=mid,cnt=a;
		m(a,mid);
		m(mid,b);
		while(l<mid || r<b)
		{
			if(r>=b ||(l<mid && A[l].fs>=A[r].fs)) 
			{
				if(A[l].fs==A[r].fs&&strcmp(A[l].name,A[r].name)>0){student Temp;
				strcpy(Temp.name,A[l].name);
				strcpy(A[l].name,A[r].name);
				strcpy(A[r].name,Temp.name);
				}
				strcpy(temp[cnt].name,A[l].name);
				temp[cnt++].fs=A[l++].fs;
			}
			else{
				strcpy(temp[cnt].name,A[r].name);
				temp[cnt++].fs=A[r++].fs;
						}
		}
		for(int i=a;i<b;i++)
		{
			strcpy(A[i].name,temp[i].name);
			A[i].fs=temp[i].fs;
		}
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].name>>A[i].fs;
	}
	m(1,n+1);
	for(int i=1;i<=n;i++)
		{
		cout<<A[i].name<<" "<<A[i].fs<<"\n";
		}
	return 0;
}

6.结构体+sort的用法

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct student{
	int chinese,math,English,total,n;
}A[310];
bool camp(student a,student b){
	if(a.total>b.total) return true;
	else if(a.total<b.total) return false;
	else{
		if(a.chinese>b.chinese) return true;
		else if(a.chinese<b.chinese) return false;
		else{
			if(a.n<b.n) return true;
			else return false;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		A[i].n=i;
		cin>>A[i].chinese>>A[i].math>>A[i].English;
		A[i].total=A[i].chinese+A[i].math+A[i].English;
	}
	sort(A+1,A+n+1,camp);
	for(int i=1;i<=5;i++)
	{
		cout<<A[i].n<<" "<<A[i].total<<"\n";
	}
	return 0;
}

7.冒泡

#include<iostream>
using namespace std;
int n,m,id[10010],s[10010],lqrs=0,lqfs;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>id[i]>>s[i];
	for(int i=0;i<n-1;i++)
		for(int j=0;j<n-1-i;j++)
		{
			if(s[j]<s[j+1])
			{
				swap(s[j],s[j+1]);
				swap(id[j],id[j+1]);
			}
			if(s[j]==s[j+1]){
			if(id[j]>id[j+1])
			{
				swap(s[j],s[j+1]);
				swap(id[j],id[j+1]);
			}
		}
	}
	m=double(m*1.5);
	lqfs=s[m-1];
	for(int i=0;i<n;i++){
		if(s[i]>=lqfs) ++lqrs;
		else break;
	}
	cout<<lqfs<<" "<<lqrs<<"\n";
	for(int i=0;i<lqrs;i++)
		cout<<id[i]<<" "<<s[i]<<"\n";
	return 0;
}

8.活用冒泡

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int d[10]={0},j[10]={0},q,x=0,y=0;
	while(cin>>q)
	{
		if(q%2==0)d[x++]=q;
		else j[y++]=q;
	}
	for(int i=0;i<x-1;i++)
		for(int j=0;j<x-1-i;j++)
		{
			if(d[j]>d[j+1])
			swap(d[j],d[j+1]);
		}
	for(int i=0;i<y-1;i++)
			for(int q=0;q<y-1-i;q++)
			{
				if(j[q]<j[q+1])
				swap(j[q],j[q+1]);
			}
	for(int i=0;i<y;i++)cout<<j[i]<<" ";
	for(int i=0;i<x;i++)cout<<d[i]<<" ";
	return 0;
}

9.字符串加冒泡

#include<cstring>
#include<string>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,q=0,p=0;
	double tall,man[110],girl[110];
	char sex[110];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>sex>>tall;
		if(strcmp(sex,"male")==0)man[q++]=tall;
		else girl[p++]=tall;
	}
	for(int i=0;i<q-1;i++)
		for(int j=0;j<q-1-i;j++)
		{
			if(man[j]>man[j+1])
				swap(man[j],man[j+1]);
		}
	for(int i=0;i<p-1;i++)
		for(int j=0;j<p-1-i;j++)
		{
			if(girl[j]<girl[j+1])
				swap(girl[j],girl[j+1]);
		}
	for(int i=0;i<q;i++)printf("%.2lf ",man[i]);
	for(int i=0;i<p;i++)printf("%.2lf ",girl[i]);
	return 0;
}

10.结构体加冒泡

#include<cstring>
#include<string>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct ill{
	char ID[20];
	int age;
	int o;
}old[110],young[110],temp;
int main(){
	int n,k=0,p=0,q=0,d;
	char s[20];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s>>d;
		k++;
		if(d>=60){
			strcpy(old[p].ID,s);
			old[p].age=d;
			old[p].o=k;
			p++;
		}
		else {
			strcpy(young[q].ID,s);
			young[q].age=d;
			young[q].o=k;
			q++;
		}
	}
	for(int i=0;i<p-1;i++)
		for(int j=0;j<p-1-i;j++)
		{
			if(old[j].age<old[j+1].age)
			{
				temp=old[j];
				old[j]=old[j+1];
				old[j+1]=temp;
			}
			else if(old[j].age==old[j+1].age&&old[j].o>old[j+1].o)
			{
				temp=old[j];
				old[j]=old[j+1];
				old[j+1]=temp;
			}
		}
	for(int i=0;i<q-1;i++)
			for(int j=0;j<q-1-i;j++)
			{
				if(young[j].o>young[j+1].o){
					temp=young[j];
					young[j]=young[j+1];
					young[j+1]=temp;
				}
			}
	for(int i=0;i<p;i++)cout<<old[i].ID<<"\n";
	for(int i=0;i<q;i++)cout<<young[i].ID<<"\n";
	return 0;
}

11.set

#include<iostream>
#include<set>
using namespace std;
int main(){
	int n,a[100];
	set<int>ans;
	cin>>n;for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans.insert(a[i]);
	}
	cout<<ans.size()<<"\n";
	for(set<int>::iterator it=ans.begin();it!=ans.end();it++)
	{
		cout<<*it<<" ";
	}
	return 0;
}

12.string加sort

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	string a[110];
	int k=0;
	bool flag;
	while(cin>>a[k]){
		flag=false;
		for(int i=0;i<k;i++)
		{
			if(a[i].compare(a[k])==0)
			{
				flag=true;
				break;
			}
		}
		if(!flag)
			k++;
	}
	sort(a,a+k);
	for(int i=0;i<k;i++)cout<<a[i]<<"\n";
	return 0;
}

13.一些细节

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[110]={0};
	int n;
	bool flag=false;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int b;
		cin>>b;
		a[b+50]++;
	}
	for(int i=0;i<100;i++)
	{
		if(a[i]>=(n+1)>>1)
		{
			flag=true;
			cout<<i-50<<" ";
		}
	}
	if(!flag)
		cout<<"no"<<"\n";
	return 0;
}

14.字符串

#include<iostream>
#include<cstring>
using namespace std;
char word[30];
int temp[30],k=0,ans,Max=0;
int main(){
	cin>>word;
	k=strlen(word);
	for(int i=0;i<k;i++)
	{
		temp[word[i]-'a']++;
	}
	for(int i=0;i<26;i++)
	{
		if(temp[i]>Max)
		{
			ans=i;
			Max=temp[i];
		}
	}
	cout<<char('a'+ans)<<' '<<Max<<'\n';
	return 0;
}

luogu
1781.字符串排序

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    string s;
    int l;
    int index;
}zt[110];
bool cmp(node a,node b){
    if(a.l>b.l) return 1;
    if(a.l==b.l)
    {
        if(a.s>b.s) return 1;
    }
     return 0;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>zt[i].s;
        zt[i].index=i;
        zt[i].l=zt[i].s.length();
    }
    sort(zt+1,zt+1+n,cmp);
    cout<<zt[1].index<<"\n"<<zt[1].s<<"\n";
    return 0;
}

我是一个局部环,你是我的唯一极大理想。