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

    目录

    7-1 统计工龄

    7-2 寻找大富翁

    7-3 点赞狂魔

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

    7-5 插入排序还是堆排序

    7-6 逆序对

    7-7 堆排序

    7-8 石子合并

    7-9 第k小

    7-10 快速排序的过程

    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

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码：C++（g++）

    1. #include 
    2. using namespace std;
    3. int main(){
    4.     map<int,int> mp;
    5.     int n;
    6.     cin>>n;
    7.     while(n--){
    8.         int x;
    9.         cin>>x;
    10.         mp[x]++;
    11.     }
    12.     for(auto i:mp)
    13.     printf("%d:%d\n", i.first, i.second);
    14. }

    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

    代码长度限制

    16 KB

    时间限制

    500 ms

    内存限制

    64 MB

    参考代码：C++（g++）

    1. #include 
    2. using namespace std;
    3. using ll=long long;
    4. vector a;
    5. bool cmp(ll a, ll b){
    6.     return a>b;
    7. }
    8. int main(){
    9.     int n,m;
    10.     cin>>n>>m;
    11.     m=min(m,n);
    12.     for(int i=0;i
    13.         ll x;
    14.         cin>>x;
    15.         a.push_back(x);
    16.     }
    17.     sort(a.begin(), a.end(), cmp);
    18.     cout<0];
    19.     for (int i = 1; i < m; i++)
    20.         cout<<" "<
    21. }

    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

    代码长度限制

    16 KB

    时间限制

    200 ms

    内存限制

    64 MB

    参考代码：C++(g++)

    1. #include 
    2. using namespace std;
    3. struct user{
    4.     string name;
    5.     int num;
    6.     int sum;
    7.     double ave;
    8. } s[105]; //name:用户名 num:点赞的不同标签的数量 sum:点赞总数 ave:标签出现次数平均值
    9. bool cmp(user a, user b){
    10.     if (a.num==b.num)return a.ave>b.ave;
    11.     return a.num>b.num;
    12. }
    13. int main(){
    14.     int n;
    15.     cin>>n;
    16.     for(int i=0;i
    17.         map<int,int>mp;
    18.         cin>>s[i].name>>s[i].sum;
    19.         for (int j=0;j
    20.             int x;
    21.             cin>>x;
    22.             mp[x]++;
    23.         }
    24.         s[i].num=mp.size();
    25.         s[i].ave=1.0*s[i].num/s[i].sum;
    26.     }
    27.     sort(s,s+n,cmp);
    28.     if(n==1)cout<0].name<<" - -"<
    29.     else if(n==2)cout<0].name<<" "<1].name<<" -"<
    30.     else cout<0].name<<" "<1].name<<" "<2].name<
    31. }

    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

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码：C++(g++)

    1. #include 
    2. using namespace std;
    3. int main(){
    4.     int n,pos,i,j,range=2,a[105],b[105];
    5.     cin>>n;
    6.     for(i=0;i
    7.         cin>>a[i];
    8.     for(i=0;i
    9.         cin>>b[i];
    10.     for(i=1;i
    11.         if(b[i]-1])break;
    12.     for(j=i;j
    13.         if (a[j] != b[j])break;
    14.     if(j==n){
    15.         printf("Insertion Sort\n");
    16.         sort(b,b+i+1);
    17.     }
    18.     else{
    19.         printf("Merge Sort\n");
    20.         while (1){
    21.             for (i=0;i
    22.                 sort(a+i*range,a+(i+1)*range);
    23.             sort(a+i*range,a+n);
    24.             for(i=0;i
    25.                 if (a[i]!=b[i])break;
    26.             if(i==n){
    27.                 range*=2;
    28.                 for(i=0;i
    29.                     sort(b+i*range,b+(i+1)*range);
    30.                 sort(b+i*range,b+n);
    31.                 break;
    32.             }
    33.             range*=2;
    34.         }
    35.     }
    36.     cout<0];
    37.     for(i=1;i
    38.         cout<<" "<
    39. }

    7-5 插入排序还是堆排序

    作者 陈越

    单位 浙江大学

    根据维基百科的定义：

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

    堆排序也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。

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

    输入格式：

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

    输出格式：

    首先在第 1 行中输出Insertion Sort表示插入排序、或Heap 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 6 0

    6 4 5 1 0 3 2 7 8 9

    输出样例 2：

    Heap Sort

    5 4 3 1 0 2 6 7 8 9

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码C++（g++）

    1. #include
    2. using namespace std;
    3. int main(){
    4. 	int array[128],answer[128],i,number,r;
    5. 	scanf("%d",&number);
    6. 	for(i=1;i<=number;i++)scanf("%d",array+i);
    7. 	for(i=1;i<=number;i++)scanf("%d",answer+i);
    8. 	for(i=2;iif(answer[i]-1])break;
    9. 	for(r=i;r<=number;r++)if(array[r]!=answer[r])break;
    10. 	if(r<=number){
    11. 		cout<<"Heap"<<" "<<"Sort"<
    12. 		for(i=2;i<=number;i++)if(answer[i]>answer[1])break;
    13. 		answer[0]=answer[i-1];
    14. 		answer[i-1]=answer[1];
    15. 		for(r=2;r-1;r*=2){
    16. 			if(answer[r+1]>answer[r]&&r+1-1)r++;
    17. 			if(answer[r]0])break;
    18. 			answer[r/2]=answer[r];
    19. 		}
    20. 		answer[r/2]=answer[0];
    21. 	}
    22. 	else{
    23. 		cout<<"Insertion"<<" "<<"Sort"<
    24. 		sort(answer+1,answer+i+1);
    25. 	}
    26. 	for(i=1;i<=number;i++){
    27. 		if(i>1)cout<<" ";
    28. 		cout<
    29. 	}
    30. }

    7-6 逆序对

    作者 c++课程组

    单位 湖州师范学院

    求逆序对。

    输入格式:

    第一行是一个整数n，（n<=1000,000）表示输入序列的长度，接下来一行是n个整数(每个数的绝对值小于109)。

    输出格式:

    一个数，表示逆序对个数(逆序即任意一对数前面的数比后面的数大即为一对逆序对)。

    输入样例:

    10

    1 3 5 7 9 8 4 2 6 10

    输出样例:

    逆序对对数可能很大，计数器要用long long：

    14

    说明：样例中如1和3不是逆序对，而3和2是1对逆序对，例子中共有14对逆序对。题目中可能有某些数字出现多次的情况。

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码C（gcc）

    1. #include 
    2. #define N 1000000
    3. int n,a[N],b[N];
    4. long long  cnt=0;
    5. void f(int L,int R){
    6.     if(L==R) return;
    7.     int m=(L+R)/2;
    8.     int k1=L,k2=m+1,k=L;
    9.     f(L,m);
    10.     f(m+1,R);
    11.     while(k1<=m&&k2<=R){
    12.         if(a[k1]<=a[k2]){
    13.             b[k]=a[k1];
    14.             k++,k1++;
    15.         }
    16.         else{
    17.             b[k]=a[k2];
    18.             k++,k2++;
    19.             cnt=cnt+m-k1+1;
    20.         }
    21.     }
    22.     while(k1<=m){
    23.          b[k]=a[k1];
    24.          k++,k1++;
    25.     }
    26.     while(k2<=R){
    27.          b[k]=a[k2];
    28.          k++,k2++;
    29.     }
    30.     for(int i=L;i<=R;i++)
    31.         a[i]=b[i];
    32. }
    33. int main(){
    34.     int i ;
    35.     scanf("%d",&n);
    36.     for(i=1;i<=n;i++)
    37.         scanf("%d",&a[i]);
    38.     f(1,n);
    39.     printf("%lld",cnt);
    40.     return 0;
    41. }

    7-7 堆排序

    作者 黄龙军

    单位 绍兴文理学院

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

    输入格式:

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

    输出格式:

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

    输入样例:

    4

    8 7 2 1

    输出样例:

    7 1 2 8

    2 1 7 8

    1 2 7 8

    来源：

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

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码：C++（g++）

    #include

    using namespace std;

    int a[105], n;

    void print(){

        cout<

        for (int i=2;i<=n;i++)

            cout<<" "<

        cout<

    }

    void sift(int k, int end){

        int i=k,j=2*i;

        while(j<=end){

            if(j

            if(a[i]

            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

            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-8 石子合并

    作者 杜祥军

    单位 青岛大学

    由n堆石子排成一排，其编号为1，2，3……，n。每堆石子有一定的质量mi(mi<=1000),现在要将这n堆石子合并成一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，由于合并顺序的不同，导致合并成一堆石子的总代价也不同，请求出最少的代价将所有石子合并为一堆。

    输入格式:

    第一行输入n。
    第二行输入n个mi。

    输出格式:

    输出一个整数，表示石子合并的最小代价。

    输入样例:

    4

    2 5 3 1

    输出样例:

    22

    代码长度限制

    16 KB

    时间限制

    1000 ms

    内存限制

    64 MB

    参考代码：C++（g++）

    1. #include
    2. using namespace std;
    3. const int INF = 100000;
    4. const int N = 205;
    5. int Min[N][N], Max[N][N], s[N][N];//求最小、最大值
    6. int sum[N];//计算前i堆石子的数量总和，sum[0]=0，w(i,j)=sum[j]-sum[i-1]
    7. int a[N];//记录各堆石子的数量
    8. int minn, maxx;
    9. void get_Min(int n) {
    10. 	for (int v = 2; v <= n; v++) {//枚举合并的堆数规模
    11. 		for (int i = 1; i <= n - v + 1; i++) {
    12. 			int j = i + v - 1;
    13. 			int tmp = sum[j] - sum[i - 1];
    14. 			int i1 = s[i][j - 1] > i ? s[i][j - 1] : i;
    15. 			int j1 = s[i + 1][j] < j ? s[i + 1][j] : j;
    16. 			Min[i][j] = Min[i][i1] + Min[i1 + 1][j];
    17. 			s[i][j] = i1;
    18. 			for (int k = i1 + 1; k <= j1; k++) {
    19. 				if (Min[i][k] + Min[k + 1][j] < Min[i][j]) {
    20. 					Min[i][j] = Min[i][k] + Min[k + 1][j];
    21. 					s[i][j] = k;
    22. 				}
    23. 			}
    24. 			Min[i][j] += tmp;
    25. 		}
    26. 	}
    27. }
    28. void straight(int a[], int n) {
    29. 	for (int i = 1; i <= n; i++) {//初始化
    30. 		Min[i][i] = 0, Max[i][i] = 0, s[i][i] = 0;
    31. 	}
    32. 	sum[0] = 0;
    33. 	for (int i = 1; i <= n; i++) {
    34. 		sum[i] = sum[i - 1] + a[i];
    35. 	}
    36. 	get_Min(n);
    37. }
    38. int main(){
    39. 	int n;
    40. 	cin >> n;
    41. 	for (int i = 1; i <= n; i++){
    42. 		cin >> a[i];
    43. 	}
    44. 	straight(a, n);
    45. 	cout << Min[1][n];
    46. 	return 0;
    47. }

    参考代码二（C++）

    思路：石子合并问题_ACdreamers的博客-CSDN博客

    1. #include 
    2. using namespace std;
    3. const int N=110;
    4. int a[N],d[N];
    5. int dp[N][N];
    6. int main() {
    7.     int n;
    8.     cin>>n;
    9.     for(int i=1;i<=n;i++) {
    10.         cin>>a[i];
    11.         d[i]=d[i-1]+a[i];
    12.     }
    13.     for(int h=1;h<=n;h++) {
    14.         for(int i=1;i<=n;i++) {
    15.             int j=i+h;
    16.             if(j>n)continue;
    17.             dp[i][j]=0x3f3f3f3f;
    18.             for(int k=i;k<=j;k++){
    19.                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
    20.             }
    21.             dp[i][j]+=d[j]-d[i-1];
    22.         }
    23.     }
    24.     cout<1][n]<
    25.     return 0;
    26. }

    7-9 第k小

    作者 严华云

    单位 湖州师范学院

    有n个数，求第k小的数。例如在数：{1 3 5 7 9 8 4 2 6 10}中，第3小的数是3 。

    输入格式:

    第一行输入两个数，n和k（n<=1000000），分别表示总的n个数和求第k小的数。第二行输入n个数( 最大数<10^7)。

    输出格式:

    一个数，表示第k小的数。

    输入样例:

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

    10 3

    1 3 5 7 9 8 4 2 6 10

    输出样例:

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

    3

    代码长度限制

    16 KB

    时间限制

    300 ms

    内存限制

    64 MB

    参考代码：c++（g++）

    1. #include 
    2. using namespace std;
    3. int a[1000005];
    4. int main(){
    5.     int n,k;
    6.     while(~scanf("%d %d",&n,&k)){
    7.         for (int i=0;i
    8.             scanf("%d",&a[i]);
    9.         sort(a,a+n);
    10.         printf("%d\n",a[k-1]);
    11.     }
    12. }

    7-10 快速排序的过程

    作者 张志梅

    单位 青岛大学

    给定n个整型元素，利用快速排序算法对其进行非递减排序，请输出每一趟Partition的结果。每次选择所处理的区间的第一个元素作为基准元素。

    输入格式:

    输入为两行，第一行为一个整数n（1

    输出格式:

    输出为若干行，每行依次输出Partition后的结果，每个元素后一个空格。

    输入样例:

    5

    4 5 3 2 1

    输出样例:

    2 1 3 4 5

    1 2 3 4 5

    1 2 3 4 5

    1 2 3 4 5

    1 2 3 4 5

    代码长度限制

    16 KB

    时间限制

    400 ms

    内存限制

    64 MB

    参考代码：C++（g++）

    1. #include 
    2. using namespace std;
    3. int n;
    4. void print(int *arr){
    5. 	for(int i=0;i
    6. 		printf("%d ",arr[i]);
    7. 	cout<
    8. }
    9. void quicksort(int *arr, int left, int right){
    10. 	if (left > right)return;  //首先判断一下传递进来的left和right合不合理
    11. 	int i = left,j = right;    //把left和right赋值给i，j作为他们的初始状态
    12. 	int pivot = arr[left];  //让最左边的元素作为支点pivot
    13. 	//不是0开始，要递归调用，比如pivot右边的子数组初始下标就不是0，所以不是arr[0]
    14. 	while (i < j){  //i与j碰到时，结束一次排序，所以i
    15. 		while (arr[j] >= pivot && i < j)
    16. 			j--;  //j（R)要找的是小于pivot的数，所以当arr[j]>=pivot时，此数不用操作，j向左移动（别忘了i
    17. 		while (arr[i] <= pivot && i < j)
    18. 			i++;  //i（L)要找的是大于pivot的数，所以当arr[i]<=pivot时，此数不用操作，i向右移动（别忘了i
    19. 		if (i < j)  //执行到这一语句，说明j和i都停下来了，若满足i
    20. 			swap(arr[i], arr[j]);
    21. 	}
    22. 	swap(arr[left], arr[i]); //支点回归它正确的位置。执行到这句的时候，即已经跳出循环了，即i和j相交了。此时交换pivot和arr[i](或arr[j])(此时是一个数）
    23. 	print(arr);
    24.     quicksort(arr, left, i - 1);  //递归pivot左边的子数组
    25. 	quicksort(arr, i + 1, right);  //递归pivot右边的子数组
    26. }
    27. int main(){
    28.   cin>>n;
    29. 	int arr[n]; 
    30. 	for(int i=0;i
    31.       scanf("%d",&arr[i]);
    32. 	quicksort(arr, 0, n-1);
    33. 	return 0;
    34. }

  • 相关阅读:
    【区块链 | 智能合约】Ethereum源代码（10）- 以太坊Downloader源码分析
    Java并发编程：如何正确使用 volatile、synchronized 和 final 关键字
    [附源码]java毕业设计医院就诊流程管理系统
    C++入门知识整理（持续更新）
    【七大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序、归并排序
    C++ 文件和流
    （附源码）springboot家庭财务分析系统 毕业设计641323
    端口映射与容器互联
    C语言--用二分法快速计算指定整数的整数平方根
    C++类与结构体、this指针（二）
  • 原文地址：https://blog.csdn.net/m0_63485942/article/details/128119452