我必须构建一个函数,该函数按行对矩阵进行排序,然后按列或其他方式对矩阵进行排序,同时保留矩阵中的值。 该矩阵是一个巨大的矩阵,所以我使用的算法必须是 nlogn 算法。
我的结构如下:
typedef struct{
unsigned int line, column;
float value;}Matrix;
Matrix matrix[size_of_matrix*size_of_matrix];
static int numb_of_matrix; /*Whenever I ask the user to insert values to the matrix, I increase this number to insert the structure inside my vector matrix*/
我还存储了用户填充的行和列的最大和最小索引,这些边界之间的索引设置为 0,因此我创建了一个 size_of_matrix*size_of_matrix 的矩阵,其中全是 0,然后我插入我的值,同时存储用户填充的行和列的最高和最低索引。
鉴于此,我需要按行的递增顺序排序,然后按列的递增顺序排序,或者反过来。 我必须知道我必须以哪种方式对矩阵进行排序的方式是,如果我需要首先按列对矩阵进行排序,则要求用户输入 C 如果我需要首先按行对矩阵进行排序,则什么都没有。
因此,如果我向矩阵介绍了以下内容:
[0,3]=1.2
[3,0]=2.1
[4,5]=2.2
[2,5]=3.2
[3,5]=4.2
然后我先按行排序,应该变成
[0,3]=1.2
[2,5]=3.2
[3,0]=2.1
[3,5]=4.2
[4,5]=2.2
如果矩阵足够小,这个问题会很快解决,但我的矩阵将有近 100 万个值,所以我不能使用冒泡排序或任何其他 n^2 排序算法。
最佳答案
您保存矩阵的格式称为三元组格式。按行或列顺序对它们进行排序意味着将它们保存为压缩稀疏列 (CSC) 或压缩稀疏行 (CSR) 格式。 大多数稀疏库都有效地实现了它们。将 CSC 转换为 CSR 或相反只是矩阵转置。如果您正在寻找一个小而高效的代码,您可以查看 SuiteSparse/CSparse 中的“cs_transpose”函数。 将三元组转换为任何压缩形式就是这样。计算每行/列中的元素数量,然后按顺序将它们放在正确的位置(如桶排序)。该算法的复杂度为 O(n),但行/列中的元素未排序。 一个简单的解决方案是调换它们。 transposition twice其实是在实践中用到的!
关于c - 按列和按行对矩阵进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50021947/