排序算法例题C，如何改写为长尾词不超过50个字？
- 内容介绍
- 文章标签
- 相关推荐
本文共计2374个文字，预计阅读时间需要10分钟。
给定一个序列 \(a_1, a_2, \ldots, a_n\)，我们需要找出所有逆序对的数量。逆序对是指序列中两个元素 \(i\) 和 \(j\)，其中 \(i a_j\)。
输入：第一行输入一个整数 \(n\)，表示序列的长度。接下来 \(n\) 行，每行输入一个整数，表示序列中的元素。
输出：输出一个整数，表示逆序对的数量。
示例：输入：
53
12
45
输出：
3
解释：逆序对有：(3, 1)，(3, 2)，(4, 1)。
1、求逆序对--归并排序
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
所有逆序对总数。
4 3 2 3 2 3 N≤10 ^5，Ai≤10 ^5。
#include<iostream>
using namespace std;
const int N=100005;
int a[N],t[N];
long long ans=0;
void msort(int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
t[k]=a[i];
i++;k++;
}else
{
t[k]=a[j];
j++;k++;
ans+=mid-i+1;//在归并排序算法基础上加上这个，累加左序列中符合条件的剩下元素个数
}
}
while(i<=mid)
{
t[k]=a[i];
i++;k++;
}
while(j<=r)
{
t[k]=a[j];
j++;k++;
}
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];
}
msort(1,n);
cout<<ans<<endl;
return 0;
}
2、谁考了第k名--冒泡排序
在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。
第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。
其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。
输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）
5 3 90788001 67.8 90788002 90.3 90788003 61 90788004 68.4 90788005 73.9 90788004 68.4
格式控制符%g，小数点右侧的尾数0不被显示；显示小数点仅当输出的小数部分不为0。
#include<iostream>
#include<cstring>
using namespace std;
const int N=10005;
int main()
{
int n,k;
string no[N];
double sc[N];
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>no[i]>>sc[i];
}
for(int i=n;i>1;i--)
{
//bool flag=false;
for(int j=1;j<i;j++)
{
if(sc[j]<sc[j+1])//从大到小排序
{
swap(sc[j],sc[j+1]);//要交换成绩和学号
swap(no[j],no[j+1]);
//flag=true;
}
}
//if(!flag)break;
}
cout<<no[k]<<' ';
printf("%g\n",sc[k]);
return 0;
}
3、奇数单增序列--冒泡排序
给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出。
第1行为 N；
第2行为 N 个正整数，其间用空格间隔。
增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。
10 1 3 2 6 5 4 9 8 7 10 1,3,5,7,9
#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int a[N];
int main()
{
int n;
memset(a,0,sizeof(a));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>1;i--)
{
bool flag=false;
for(int j=1;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
flag=true;
}
}
if(!flag)break;
}
bool first=true;//标记第一个输出的元素
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
if(first)
{
cout<<a[i];
first=false;
}else
{
cout<<","<<a[i];
}
}
}
return 0;
}
4、奖学金--sort排序函数
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279 7 279 则按输出错误处理，不能得分。
包含n+1行:
第1行为一个正整数n（小于300），表示该校参加评选的学生人数。
第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为 j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1∼n (恰好是输入数据的行号减1)。
共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 样例输入#2：
8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 样例输出#2：
8 265 2 264 6 264 1 258 5 258
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
struct Stu
{
int no;//学号
int c;//语文成绩
int sum;//总分
}a[N];
//重定义比较规则
bool cmp(Stu x,Stu y)
{
if(x.sum==y.sum)
{
if(x.c==y.c)
{
return x.no<y.no;
}else
{
return x.c>y.c;
}
}else
{
return x.sum>y.sum;
}
}
int main()
{
int n;
cin>>n;
int u,v;//数学、英语成绩
for(int i=0;i<n;i++)
{
cin>>a[i].c>>u>>v;
a[i].no=i+1;
a[i].sum=a[i].c+u+v;
}
sort(a,a+n,cmp);//直接使用sort函数
//这里分一下，人数小于5个时，直接输出前n个
if(n<5)
{
for(int i=0;i<n;i++)
{
cout<<a[i].no<<" "<<a[i].sum<<endl;
}
}else
{
for(int i=0;i<5;i++)//只输出前5个
{
cout<<a[i].no<<" "<<a[i].sum<<endl;
}
}
return 0;
}
5、出现次数超过一半的数--桶排序
给出一个含有n（0 < n <= 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大于-50且小于50。
第一行包含一个整数n，表示数组大小；
第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。
如果存在这样的数，输出这个数；否则输出no。
3 1 2 2 2
分析：数字大小有范围，可以使用桶排序算法，但是有负数，所以每个数字加上100，让范围变成51—149
#include<iostream>
using namespace std;
int main()
{
int n,m,a[1005]={0};
cin>>n;
int t=n;
while(n)
{
n--;
cin>>m;
a[m+100]++;// 桶排序，放入对应的桶，数量加1
if(a[m+100]>t/2)
{
cout<<m<<endl;
return 0;
}
}
cout<<"no"<<endl;
return 0;
}
6、单词排序
输入一行单词序列，相邻单词之间由1个或多个空格间隔，请按照字典序输出这些单词，要求重复的单词只输出一次。（区分大小写）
一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。
按字典序输出这些单词，重复的单词只输出一次。
She wants to go to Peking University to study Chinese Chinese Peking She University go study to wants
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
string str[105],s;// 定义一个字符串数组
int n=1;
while(cin>>s)//反复读入，直至文件尾
{
str[n++]=s;
}
sort(str,str+n);//直接使用sort函数，string数组也可以使用它
for(int i=1;i<=n;i++)
{
if(str[i-1]!=str[i])//与前一个相等就不输出
cout<<str[i]<<endl;
}
return 0;
}
本文共计2374个文字，预计阅读时间需要10分钟。
给定一个序列 \(a_1, a_2, \ldots, a_n\)，我们需要找出所有逆序对的数量。逆序对是指序列中两个元素 \(i\) 和 \(j\)，其中 \(i a_j\)。
输入：第一行输入一个整数 \(n\)，表示序列的长度。接下来 \(n\) 行，每行输入一个整数，表示序列中的元素。
输出：输出一个整数，表示逆序对的数量。
示例：输入：
53
12
45
输出：
3
解释：逆序对有：(3, 1)，(3, 2)，(4, 1)。
1、求逆序对--归并排序
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
所有逆序对总数。
4 3 2 3 2 3 N≤10 ^5，Ai≤10 ^5。
#include<iostream>
using namespace std;
const int N=100005;
int a[N],t[N];
long long ans=0;
void msort(int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
t[k]=a[i];
i++;k++;
}else
{
t[k]=a[j];
j++;k++;
ans+=mid-i+1;//在归并排序算法基础上加上这个，累加左序列中符合条件的剩下元素个数
}
}
while(i<=mid)
{
t[k]=a[i];
i++;k++;
}
while(j<=r)
{
t[k]=a[j];
j++;k++;
}
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];
}
msort(1,n);
cout<<ans<<endl;
return 0;
}
2、谁考了第k名--冒泡排序
在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。
第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。
其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。
输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）
5 3 90788001 67.8 90788002 90.3 90788003 61 90788004 68.4 90788005 73.9 90788004 68.4
格式控制符%g，小数点右侧的尾数0不被显示；显示小数点仅当输出的小数部分不为0。
#include<iostream>
#include<cstring>
using namespace std;
const int N=10005;
int main()
{
int n,k;
string no[N];
double sc[N];
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>no[i]>>sc[i];
}
for(int i=n;i>1;i--)
{
//bool flag=false;
for(int j=1;j<i;j++)
{
if(sc[j]<sc[j+1])//从大到小排序
{
swap(sc[j],sc[j+1]);//要交换成绩和学号
swap(no[j],no[j+1]);
//flag=true;
}
}
//if(!flag)break;
}
cout<<no[k]<<' ';
printf("%g\n",sc[k]);
return 0;
}
3、奇数单增序列--冒泡排序
给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出。
第1行为 N；
第2行为 N 个正整数，其间用空格间隔。
增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。
10 1 3 2 6 5 4 9 8 7 10 1,3,5,7,9
#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int a[N];
int main()
{
int n;
memset(a,0,sizeof(a));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>1;i--)
{
bool flag=false;
for(int j=1;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
flag=true;
}
}
if(!flag)break;
}
bool first=true;//标记第一个输出的元素
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
if(first)
{
cout<<a[i];
first=false;
}else
{
cout<<","<<a[i];
}
}
}
return 0;
}
4、奖学金--sort排序函数
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279 7 279 则按输出错误处理，不能得分。
包含n+1行:
第1行为一个正整数n（小于300），表示该校参加评选的学生人数。
第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为 j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1∼n (恰好是输入数据的行号减1)。
共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 样例输入#2：
8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 样例输出#2：
8 265 2 264 6 264 1 258 5 258
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
struct Stu
{
int no;//学号
int c;//语文成绩
int sum;//总分
}a[N];
//重定义比较规则
bool cmp(Stu x,Stu y)
{
if(x.sum==y.sum)
{
if(x.c==y.c)
{
return x.no<y.no;
}else
{
return x.c>y.c;
}
}else
{
return x.sum>y.sum;
}
}
int main()
{
int n;
cin>>n;
int u,v;//数学、英语成绩
for(int i=0;i<n;i++)
{
cin>>a[i].c>>u>>v;
a[i].no=i+1;
a[i].sum=a[i].c+u+v;
}
sort(a,a+n,cmp);//直接使用sort函数
//这里分一下，人数小于5个时，直接输出前n个
if(n<5)
{
for(int i=0;i<n;i++)
{
cout<<a[i].no<<" "<<a[i].sum<<endl;
}
}else
{
for(int i=0;i<5;i++)//只输出前5个
{
cout<<a[i].no<<" "<<a[i].sum<<endl;
}
}
return 0;
}
5、出现次数超过一半的数--桶排序
给出一个含有n（0 < n <= 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大于-50且小于50。
第一行包含一个整数n，表示数组大小；
第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。
如果存在这样的数，输出这个数；否则输出no。
3 1 2 2 2
分析：数字大小有范围，可以使用桶排序算法，但是有负数，所以每个数字加上100，让范围变成51—149
#include<iostream>
using namespace std;
int main()
{
int n,m,a[1005]={0};
cin>>n;
int t=n;
while(n)
{
n--;
cin>>m;
a[m+100]++;// 桶排序，放入对应的桶，数量加1
if(a[m+100]>t/2)
{
cout<<m<<endl;
return 0;
}
}
cout<<"no"<<endl;
return 0;
}
6、单词排序
输入一行单词序列，相邻单词之间由1个或多个空格间隔，请按照字典序输出这些单词，要求重复的单词只输出一次。（区分大小写）
一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。
按字典序输出这些单词，重复的单词只输出一次。
She wants to go to Peking University to study Chinese Chinese Peking She University go study to wants
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
string str[105],s;// 定义一个字符串数组
int n=1;
while(cin>>s)//反复读入，直至文件尾
{
str[n++]=s;
}
sort(str,str+n);//直接使用sort函数，string数组也可以使用它
for(int i=1;i<=n;i++)
{
if(str[i-1]!=str[i])//与前一个相等就不输出
cout<<str[i]<<endl;
}
return 0;
}