C++程序 将矩阵按行和列排序

给定一个 n x n 的矩阵。问题是按行和列排序矩阵。

例子:

输入 : mat[][] = { {4, 1, 3},
                    {9, 6, 8},
                    {5, 2, 7} }
输出 : 1 3 4
         2 5 7
         6 8 9

输入 : mat[][] = { {12, 7, 1, 8},
                    {20, 9, 11, 2},
                    {15, 4, 5, 13},
                    {3, 18, 10, 6} } 
输出 : 1 5 8 12
         2 6 10 15
         3 7 11 18
         4 9 13 20

方法: 以下是步骤:

1. 按矩阵的每行排序。
2. 得到矩阵的转置。
3. 再按矩阵的每行排序。
4. 再得到矩阵的转置。

使用C ++ STL sort()对每行矩阵进行排序的算法:

for (int i = 0 ; i < n; i++)
    sort(mat[i], mat[i] + n);

获取矩阵的转置的算法:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int temp = mat[i][j];
        mat[i][j] = mat[j][i];
        mat[j][i] = temp;
    }
}

// C++ implementation to sort the matrix row-wise
// and column-wise
#include <bits/stdc++.h>
  
using namespace std;
  
#define MAX_SIZE 10
  
// function to sort each row of the matrix
void sortByRow(int mat[MAX_SIZE][MAX_SIZE], int n)
{
    for (int i = 0; i < n; i++)
  
        // sorting row number 'i'
        sort(mat[i], mat[i] + n);
}
  
// function to find transpose of the matrix
void transpose(int mat[MAX_SIZE][MAX_SIZE], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) 
  
            // swapping element at index (i, j) 
            // by element at index (j, i)
            swap(mat[i][j], mat[j][i]);
}
  
// function to sort the matrix row-wise
// and column-wise
void sortMatRowAndColWise(int mat[MAX_SIZE][MAX_SIZE],
                                               int n)
{
    // sort rows of mat[][]
    sortByRow(mat, n);
  
    // get transpose of mat[][]
    transpose(mat, n);
  
    // again sort rows of mat[][]
    sortByRow(mat, n);
  
    // again get transpose of mat[][]
    transpose(mat, n);
}
  
// function to print the matrix
void printMat(int mat[MAX_SIZE][MAX_SIZE], int n)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
}
  
// Driver program to test above
int main()
{
    int mat[MAX_SIZE][MAX_SIZE] = { { 4, 1, 3 },
                            { 9, 6, 8 },
                            { 5, 2, 7 } };
    int n = 3;
  
    cout << "原始矩阵:
";
    printMat(mat, n);
  
    sortMatRowAndColWise(mat, n);
  
    cout << "
排序后的矩阵:
";
    printMat(mat, n);
  
    return 0;
}  

输出:

原始矩阵:
4 1 3
9 6 8
5 2 7

排序后的矩阵:
1 3 4
2 5 7
6 8 9

时间复杂度: O(n 2 log 2 n)。

辅助空间：O(1)。