行排序列排序矩阵

Question

有没有人能推荐一个算法，用来生成一个行和列都排序的二维矩阵，给定一个整数列表？

我的意思是，这个矩阵的所有行和所有列都应该是有序的，最好是整体升序或降序。

我想到的办法是，先把这些元素排序，然后从矩阵的左上角（0,0）开始放第一个元素，接着放到（0,1），再放到（1,0），然后是（0,2），再到（2,0），依此类推。当某一行或某一列放满了，就换到下一行或下一列继续放。

我的算法示例 -

元素是从零开始的自然数。

3行5列的矩阵 -

0        1      3   5   7 
2        6      9   11  13
4        8      10  12  14

5行7列的矩阵 -

0     1      3     5     7   9  11
2     10     13   15    17  19  21
4     12     18   23    24  26  28
6     14     20   25    29  30  32
8     16     22   27    31  33  34

这样做对吗？有没有人能提出一个不同的算法，并给出相应的代码（Python/C）？

谢谢大家。

补充 - 希望不使用Python中的其他库，比如numpy等。有没有办法用简单的老式Python代码来实现这个？

Answer 1

 1  2  3  4  5
 6  7  8  9 10
 11 12 13 14 15 

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 2

你需要在一个循环里面再用一个循环：

举个例子：

int matrix[4][4]; //your matrix is a 4x4 in this example
int sum[]={0,0,0,0};

for(int index=0; index<=4; index++){
    for(int i=0;i<=4;i++){  //here sum the row
        sum[index]+=matrix[index][i];
    }

    for(int i=0;i<=4;i++){  //here sum the column
        sum[index]+=matrix[i][index];
    }
}

最后，你会得到第一列和第一行的总和在sum[0]里，第二列和第二行的总和在sum[1]里，依此类推...

Answer 3

假设有一个 RxC 的数组，其中 R 代表行数，C 代表列数，并且 R 大于 C。很明显，任务至少需要对所有的行进行排序，这个过程的复杂度是 O(R.C.Log(C))。把这个和全局排序的复杂度 O(R.C.Log(R.C)) = O(R.C.Log(C)) 相比，你会发现其实没必要去寻找更快的方法，除非 R 远远大于 C。

Answer 4

把你的2x2矩阵当成一个一维数组来处理，然后用qsort()函数对它进行排序。这样就搞定了！

int arr[3][3];
for (int row = 0; row < 3; row++) {
    for (int col = 0; col < 3; col++) {
        arr[row][col] = row * 3 + col;
    }
}
qsort(arr[0], 9, sizeof (int), delta);

---

int delta(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return *aa - *bb;
}