数据结构与算法实验8——排序

7-1 统计工龄

给定公司 n 名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。

输入格式:

输入首先给出正整数 n（≤105），即员工总人数；随后给出 n 个整数，即每个员工的工龄，范围在 [0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

#include<stdio.h>
int main()
{int n,t;int age[51]={0};scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&t);age[t]++;}for(int i=0;i<51;i++){if(age[i]>0)printf("%d:%d\n",i,age[i]);}return 0;
}

 7-2 寻找大富翁

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

输入格式:

输入首先给出两个正整数N（≤106）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。

输出格式:

在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。

输入样例:

8 3
8 12 7 3 20 9 5 18

输出样例:

20 18 12

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;scanf("%d %d",&n,&m);m=min(m,n);long long int a[n];for(int i=0;i<n;i++){scanf("%lld",&a[i]);}for(int i=0;i<m;i++){for(int j=i+1;j<n;j++){if(a[j]>a[i])swap(a[j],a[i]);}}for(int i=0;i<m;i++){if(i==0)printf("%lld",a[i]);elseprintf(" %lld",a[i]);}return 0;
}

 7-3 点赞狂魔

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：

输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F1​⋯FK​”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fi​（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。

输出格式：

统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：

5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14

输出样例：

jack chris john

#include<bits/stdc++.h>
using namespace std;
struct user
{string name;int num;  // num是点赞不同标签的数量int sum;  // sum是点赞总数double ave;  // ave是点赞平均值
} s[105];
bool cmp(user a, user b)
{if (a.num == b.num)return a.ave > b.ave;return a.num > b.num;
}
int main()
{int n;cin >> n;for (int i = 0; i < n; i++){map<int, int> mp;cin >> s[i].name >> s[i].sum;for (int j = 0; j < s[i].sum; j++){int x;cin >> x;mp[x]++;}s[i].num = mp.size();s[i].ave = 1.0 * s[i].num / s[i].sum;}for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){if (cmp(s[j], s[i])){swap(s[j],s[i]);}}}if (n == 1)cout << s[0].name << " - -" << endl;else if (n == 2)cout << s[0].name << " " << s[1].name << " -" << endl;elsecout << s[0].name << " " << s[1].name << " " << s[2].name << endl;return 0;
}

7-4 插入排序还是归并排序

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 n (≤100)；随后一行给出原始序列的 n 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

#include <bits/stdc++.h>
using namespace std;
int main(){int n,pos,i,j,range=2,a[105],b[105];cin>>n;for(i=0;i<n;i++)cin>>a[i];for(i=0;i<n;i++)cin>>b[i];for(i=1;i<n;i++)if(b[i]<b[i-1])break;for(j=i;j<n;j++)if (a[j] != b[j])break;if(j==n){printf("Insertion Sort\n");sort(b,b+i+1);}else{printf("Merge Sort\n");while (1){for (i=0;i<n/range;i++)sort(a+i*range,a+(i+1)*range);sort(a+i*range,a+n);for(i=0;i<n;i++)if (a[i]!=b[i])break;if(i==n){range*=2;for(i=0;i<n/range;i++)sort(b+i*range,b+(i+1)*range);sort(b+i*range,b+n);break;}range*=2;}}cout<<b[0];for(i=1;i<n;i++)cout<<" "<<b[i];
}

7-5 逆序对

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai​>aj​ 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式:

第一行，一个数 n，表示序列中有 n个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。

输出格式:

输出序列中逆序对的数目。

输入样例:

在这里给出一组输入。例如：

6
5 4 2 6 3 1

输出样例:

在这里给出相应的输出。例如：

11

提示

对于 25% 的数据，n≤2500
对于 50% 的数据，n≤4×104。
对于所有数据，n≤5×105
请使用较快的输入输出

#include <stdio.h>
#define N 1000000
int n,a[N],b[N];
long long  cnt=0;
void f(int L,int R){if(L==R) return;int m=(L+R)/2;int k1=L,k2=m+1,k=L;f(L,m);f(m+1,R);while(k1<=m&&k2<=R){if(a[k1]<=a[k2]){b[k]=a[k1];k++,k1++;}else{b[k]=a[k2];k++,k2++;cnt=cnt+m-k1+1;}}while(k1<=m){b[k]=a[k1];k++,k1++;}while(k2<=R){b[k]=a[k2];k++,k2++;}for(int i=L;i<=R;i++)a[i]=b[i];
}
int main(){int i ;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);f(1,n);printf("%lld",cnt);return 0;
}

7-6 堆排序

给定一个整数序列，请按非递减序输出采用堆排序的各趟排序后的结果。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。

输出格式:

对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。

输入样例:

4
8 7 2 1
8
40 55 49 73 12 27 98 81

输出样例:

7 1 2 8
2 1 7 8
1 2 7 8
81 73 49 55 12 27 40 98
73 55 49 40 12 27 81 98
55 40 49 27 12 73 81 98
49 40 12 27 55 73 81 98
40 27 12 49 55 73 81 98
27 12 40 49 55 73 81 98
12 27 40 49 55 73 81 98

来源：

[1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）,上海: 上海交通大学出版社, 2023. ISBN: 9787313280732

#include <bits/stdc++.h>using namespace std;int a[105], n;void print(){cout<<a[1];for (int i=2;i<=n;i++)cout<<" "<<a[i];cout<<endl;}void sift(int k, int end){int i=k,j=2*i;while(j<=end){if(j<end&&a[j]<a[j+1])j++;if(a[i]<a[j])swap(a[i], a[j]);i=j;j=2*i;}}void heapsort(int n){for(int k=n/2;k>=1;k--)sift(k,n);for(int k=1;k<n;k++){swap(a[1],a[n-k+1]);sift(1,n-k);print();}}int main(){while (~scanf("%d", &n)){for (int i = 1; i <= n; i++)scanf("%d", &a[i]);heapsort(n);}}

7-7 寻找第k小的数

给定若干整数，请设计一个高效的算法，确定第k小的数。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数n，k（1≤k≤n≤1000000）。第2行输入n个整数，每个数据的取值范围在0到1000000之间。

输出格式:

对于每组测试，输出第k小的数。

输入样例:

5 3
1 2 2 2 1
9 3
1 2 3 4 5 6 9 8 7

输出样例:

2
3

提示:

如果提交后超时，请注意需要设计的是高效的算法！如果你初学《数据结构》，暂时设计不出来，请学完相关知识再回头来做。
也可以使用STL之sort、nth_element函数求解。

另外，由于输入数据特别多，为减少输入数据的耗时，建议使用以下的输入外挂函数：

void scan_d(int &num)    
{char in;in=getchar();while(in<'0'||in>'9') in=getchar(); num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}
}

调用方法如下：

int n;
scan_d(n);

或者使用scanf()函数进行输入；
或8者使用以下语句提高cin、cout的效率：

ios::sync_with_stdio(false);

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

7-8 链式基数排序

实现链式基数排序，待排序关键字n满足1≤n≤1000，最大关键字数位≤5。

输入样例：

第一行输入待排序个数n（1≤n≤1000）,再输入n个数(n的数位≤5)。

10
278 109 63 930 589 184 505 269 8 83

输出样例：

输出每趟分配-收集后链表中的关键字，趟数为序列中最大值的数位（如样例中930的数位为3），每行结尾有空格。

930 63 83 184 505 278 8 109 589 269 
505 8 109 930 63 269 278 83 184 589 
8 63 83 109 184 269 278 505 589 930 

#include<bits/stdc++.h>
using namespace std;struct node{int number;struct node * next;
};int num, maxN = 1;
node *head;
queue<node*> q[10];void init() {cin >> num;head = (node*) malloc(sizeof(node));head->next = nullptr;node *temp, *p = head;for (int i = 0; i < num; ++i) {temp = (node*) malloc(sizeof(node));p->next = temp;temp->next = nullptr;p = temp;cin >> temp->number;while (temp->number >= maxN) maxN *= 10;}
}
void printOut() {node *p = head->next;while (p != nullptr) {cout << p->number << ' ';p = p->next;}cout << endl;
}
void CS() {for (auto &i: q)while (!i.empty()) i.pop();node *p;for (int position = 1; position < maxN; position *= 10) {p = head->next;while (p != nullptr) {q[p->number / position % 10].push(p);p = p->next;}p = head;for (auto & i : q)while (!i.empty()) {p->next = i.front();p = p->next;p->next = nullptr;i.pop();}printOut();}
}
int main() {init();CS();
}