对nxn矩阵进行排序(2D数组)
在编程测试中，我被要求编写一个Java程序来执行3x3矩阵的排序。也就是说，我得到了一个矩阵(一个二维数组，比如m[3][3])
2 6 1
3 5 7
4 8 9我被要求对这个矩阵进行排序，它应该给出一个输出矩阵。
1 2 3
4 5 6
7 8 9 我所做的就是把这个3x3矩阵转换成一个一维数组
a[9] = {2,6,1,3,5,7,4,8,9}并对该数组执行冒泡排序，并将结果数组转换回2D数组。
我对这种方法不满意，因为我觉得这种方法很俗气。有没有更好的方法。
编辑：我想删除数组转换部分。任何排序算法都可以使用，并希望对矩阵(2D数组)本身执行排序。
回答 5
Stack Overflow用户
发布于 2015-06-30 10:04:43
在奇怪的需求下，您可以创建一个由输入矩阵支持的视图列表，并使用标准的Collections.sort对其进行排序。
public static void sortMatrix(final int[][] matrix) {
// Assuming the matrix is rectangular
final int n = matrix.length;
final int m = matrix[0].length;
List<Integer> list = new AbstractList<Integer>() {
@Override
public Integer set(int index, Integer element) {
return matrix[index/m][index%m] = element;
}
@Override
public Integer get(int index) {
return matrix[index/m][index%m];
}
@Override
public int size() {
return n*m;
}
};
Collections.sort(list);
}这里我们只定义了我们自己的get和set方法，它们改变了相应的矩阵元素。用法示例：
int[][] matrix = {{2,6,1},{3,5,7},{4,8,9}};
sortMatrix(matrix);
System.out.println(Arrays.deepToString(matrix));输出：
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]Stack Overflow用户
发布于 2015-06-30 09:57:20
为了减少时间复杂度，您可以使用其他排序算法，比如快速排序或基排序(因为您只处理数字)。
将矩阵转换为数组不是主要的时间消耗方法，但排序是。所以对此进行优化，然后再尝试不同的方法。
编辑：
根据您的数据布局m[3][3]，您可以使用桶分类 (如果使用m[1000][1000]，这可能会带来更大的性能增益。因为您已经有了可以排序的桶，这将消除首先转换它的必要性。
Stack Overflow用户
发布于 2015-06-30 10:16:31
public int[][] sortMatrix(int matrix[][], int r, int c) {
for (int k = 0; k < r * c; k++) {
Integer current = null;
Integer previous = null;
Integer currentI = null;
Integer currentJ = null;
Integer previousI = null;
Integer previousJ = null;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
current = matrix[i][j];
currentI = i;
currentJ = j;
if (previous != null) {
if (current < previous) {
matrix[currentI][currentJ] = previous;
matrix[previousI][previousJ] = current;
}
}
previous = matrix[i][j];
previousI = i;
previousJ = j;
}
}
}
return matrix;
}https://stackoverflow.com/questions/31135058
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号