[数据结构与算法]2021秋季《数据结构》_ EOJ.1061 二维数组排序

题目

有一个 n 行组成的两维整数数组 (每行有m 个元素，)，对数组的行按以下顺序排序：按每行所有元素值的和从小到大排序。行的和相同时比较行内第 1 个元素的值，小的排在前面，若第 1 个元素的值也相等，则比较第 2 个元素，以此类推。

只需按要求写出函数定义，并使用给定的测试程序测试你所定义函数的正确性。
不要改动测试程序。测试正确后，将测试程序和函数定义一起提交。

#define M 100
//********** Specification of SortLines**********
void SortLines(int (p)[M], int n, int m);
/ PreCondition:
p points to a two-dimensional array with n lines and
m integers in each line
PostCondition:
array is sorted satisfying to the specification
*/

/**************************************************************/
/ /
/ DON’T MODIFY main function ANYWAY! /
/ /
/****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 100
#define N 100
// Specification of SortLines **********
void SortLines(int (p)[M], int n, int m)
/ PreCondition:
p points to a two-dimensional array with n lines and
m integers in each line
PostCondition:
array is sorted satisfying to the specification
/
{ //TODO: your function definition
}
/*****************/
int main()
{
int a[N][M];
int n,m,i,j;
int t,cas;
scanf("%d",&cas);
for(t=0; t<cas; t++)
{
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for (i=0; i<n; i++)
for (j=0; j<m; j++)
scanf("%d",&a[i][j]);
/ function SortLines is called here *****/
SortLines(a,n,m);
//
printf(“case #%d:\n”,t);
for (i=0; i<n; i++)
for (j=0; j<m; j++)
printf("%d%c",a[i][j],j<m-1?’ ‘:’\n’);
}
return 0;
}

思路

暴力遍历比较和交换，注意点体现在注释中

代码

#include <bits/stdc++.h>
using namespace std;
#define M 100
#define N 100

long long getSum(int* a, int m)
{
    long long res = 0;
    for (int i = 0; i < m; i++)
        res += a[i];
    return res;
}

void swapLine(int* a, int* b, int m)
{
    for (int i = 0; i < m; i++)
    {
        int tmp = a[i];
        a[i] = b[i];
        b[i] = tmp;
    }
}

void SortLines(int(*p)[M], int n, int m)
{
    for (int i = 0; i < n - 1; i++)
    {
        // long long res1 = getSum(p[i], m);  
        // 由于p[i]会通过swapLine改变，所以需要在内循环中求和，而不是外循环
        for (int j = i + 1; j < n; j++)
        {
            long long res1 = getSum(p[i], m);
            long long res2 = getSum(p[j], m);
            if (res1 != res2)
            {
                if (res1 > res2)
                    swapLine(p[i], p[j], m);
            }
            else
            {
                int idx = 0;
                while (p[i][idx] == p[j][idx]) idx++;
                if (p[i][idx] > p[j][idx])
                    swapLine(p[i], p[j], m);
            }
        }
    }
}

int main()
{
    int a[N][M];
    int n, m, i, j;
    int t, cas;
    scanf("%d", &cas);
    for (t = 0; t < cas; t++)
    {
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n, &m);
        for (i = 0; i < n; i++)
            for (j = 0; j < m; j++)
                scanf("%d", &a[i][j]);

        SortLines(a, n, m);

        printf("case #%d:\n", t);
        for (i = 0; i < n; i++)
            for (j = 0; j < m; j++)
                printf("%d%c", a[i][j], j < m - 1 ? ' ' : '\n');
    }
    return 0;
}