C++程序 将给定矩阵排序

给定一个n×n矩阵。问题是以严格的顺序对给定的矩阵进行排序。这里严格的顺序是指以这样的方式对矩阵进行排序，使得一行中的所有元素按递增顺序排序，并且对于行’i’，其中1 <= i <= n-1，第一行元素’i’大于等于行’ i-1’的最后一个元素。

示例：

Input : mat[][] = { {5, 4, 7},
                    {1, 3, 8},
                    {2, 9, 6} }
Output : 1 2 3
         4 5 6
         7 8 9

方法： 创建一个大小为n^2的 temp[] 数组。从第一行开始，将给定矩阵的元素依次复制到temp[]中。对temp[]进行排序。现在逐一将temp[]的元素复制回给定矩阵。

// C ++ implementation to sort the given matrix
#include <bits/stdc++.h>
using namespace std;
  
#define SIZE 10
  
// function to sort the given matrix
void sortMat(int mat[SIZE][SIZE], int n)
{
    // temporary matrix of size n^2
    int temp[n * n];
    int k = 0;
  
    // copy the elements of matrix one by one
    // into temp[]
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            temp[k++] = mat[i][j];
  
    // sort temp[]
    sort(temp, temp + k);
      
    // copy the elements of temp[] one by one
    // in mat[][]
    k = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mat[i][j] = temp[k++];
}
  
// function to print the given matrix
void printMat(int mat[SIZE][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[SIZE][SIZE] = { { 5, 4, 7 },
                            { 1, 3, 8 },
                            { 2, 9, 6 } };
    int n = 3;
  
    cout << "Original Matrix:
";
    printMat(mat, n);
  
    sortMat(mat, n);
  
    cout << "
Matrix After Sorting:
";
    printMat(mat, n);
  
    return 0;
}  

输出：

Original Matrix:
5 4 7
1 3 8
2 9 6

Matrix After Sorting:
1 2 3
4 5 6
7 8 9

时间复杂度：O（n 2 log 2 n）。

辅助空间：O（n 2 ）。