矩阵排序之稳定排序(结构体数组排序)题解

小半 • 2023年2月15日上午10:12 • 软件工程 • 阅读 282

矩阵排序（easy version）

时间限制: 1 Sec 内存限制: 128 MB

题目描述

给你一个大小为n*n的矩阵，矩阵里每个数均不相同，你需要对这个矩阵进行q次排序。
每一次排序会给你一个数 bi，你需要将当前矩阵的行按照第bi列的数进行稳定排序（稳定排序是指排序时相同的值的相对顺序不发生改变）
比如矩阵
4 5 6
1 2 3
3 2 7
如果按照第二列（5，2，2）进行排序的话
排序结果为
1 2 3
3 2 7
4 5 6

输入

第一行n（1<=n<=200）
第2到n+1行为输入的矩阵，每行n个数，(1<=aij<=1000000)
a11 , a12 … a1n
a21 , a22 … a2n
…
an1 , an2 … ann
注：这里n*n个数均不相同
接下来一个数q（1<=q<=200），代表要排序的次数
接下来一行q个数，代表要排序的列数 bi

输出

排序后的矩阵

样例输入

样例输出

1 2 3
4 5 6
7 8 9

提示

第一次将排序按照第二列的数排序后的结果为
1 2 3
4 5 6
7 8 9
第二次将排序按照第三列的数排序后的结果为
1 2 3
4 5 6
7 8 9

已AC代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N  = 210;
int n,m;
int num;
typedef struct amap{
    int b[N];
}amap;

amap a[N];

int comp(amap x,amap y)      
{
     if (x.b[num-1] < y.b[num-1]){
         return 1;
     }
     else{
         return 0;
     }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i].b[j];
        }
    }
    cin>>m;
    while(m--){
        cin>>num;
        sort(a,a+n,comp);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<a[i].b[j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

思路：

使用结构体数组排序的方法。

关键：

1、num全局变量的设置：方便comp函数的编写

2、函数comp的编写

3、sort函数里变量的传入：由于我们编写的comp的对象就是结构体个体，所以传入的就是结构体数组的首地址和尾地址