相对于主对角线对二维数组进行排序

Question

给定一个大小为 NxN 的二维数组 T，其中填充了各种自然数（它们不必按顺序排序任何方式如下例所示。）。我的任务是编写一个程序，以这样一种方式转换数组，即位于主对角线上方的所有元素都大于位于对角线上的每个元素，并且位于主对角线下方的所有元素都小于对角线上的每个元素.

例如： T 看起来像这样：
[2,3,5]
[7,11,13]
[17,19,23]
和其中之一可能的解决方案是：
[13,19,23]
[3,7,17]
[5,2,11]

我不知道该怎么做。有人知道这里应该使用什么算法吗？

Answer 1

假设矩阵是 NxN。
将所有 N² 个值放在一个数组中。
使用您喜欢的任何方法（升序）对数组进行排序。
在您的最终数组中，第一个 (N²-N)/2 个值位于对角线下方，随后的 N 个值位于对角线，最后的 (N²-N)/2 个值位于对角线上方。

以下 pseudo-code 应该完成这项工作：

mat <- array[N][N] // To be initialized.
vec <- array[N*N]
for i : 0 to (N-1)
  for j : 0 to (N-1)
    vec[i*N+j]=mat[i][j]
  next j
next i
sort(vec)
p_below <- 0
p_diag <- (N*N-N)/2
p_above <- (N*N+N)/2

for i : 0 to (N-1)
  for j : 0 to (N-1)
    if (i>j)
      mat[i][j] = vec[p_above]
      p_above <- p_above + 1
    endif
    if (i<j)
      mat[i][j] = vec[p_below]
      p_below <- p_below + 1
    endif
    if (i=j)
      mat[i][j] = vec[p_diag]
      p_diag <- p_diag + 1
    endif
  next j
next i

通过使用（相当复杂的）自定义排序运算符直接对矩阵进行排序，可以严重优化代码，因此可以“就地”排序。从技术上讲，您将在矩阵索引与表示“对角线下方”、“对角线”和“对角线上方”索引的分区索引集之间进行双射。

但我不确定它本身是否可以被视为一种算法，因为它将高度依赖于使用的语言 AND 你如何在内部存储你的矩阵（以及如何使用 iterators/indices）。我可以用 C++ 写一个，但我缺乏知识，无法在 Python.

中为您提供这样的运算符

显然，如果您不能使用标准排序函数（因为它只能用于数组以外的任何东西），那么您可以使用算法内置的棘手比较编写自己的函数。

对于这么小的矩阵，即使 bubble-sort 也能正常工作，但显然至少实现快速排序会更好。

关于优化的要素：

首先，我们讨论从矩阵坐标[x][y]到[i]的平凡双射：i=x+y*N。反转显然是x=floor(i/N) & y=i mod N。然后，您可以将矩阵解析为向量。这已经是我在初始化 vec 的第一部分中所做的，顺便说一句。

有了矩阵坐标，就很简单了：

对角线是 x=y.
“下方”分区无处不在x<y。
“上方”分区无处不在x>y。

看下面3x3矩阵的坐标，知道了就很明显了

0,0  1,0  2,0
0,1  1,1  2,1
0,2  1,2  2,2

我们已经知道有序向量将由三部分组成：首先是“下方”分区，然后是“对角线”分区，然后是“上方”分区。

下一个双射更棘手，因为它需要分段线性函数或 look-up table。第一个不需要额外的内存，但会使用更多 CPU 功率，第二个使用与矩阵一样多的内存，但需要更少的 CPU 功率。与往常一样，速度优化通常会消耗内存。如果内存不足是因为你使用了巨大的矩阵，那么你会更喜欢一个函数。

为了缩短一点，我将仅针对“下方”分区进行说明。在向量中，(N-1) 个第一个元素将属于第一列。然后，第二列有 (N-2) 个元素，第三列有 (N-3) 个元素，直到第 (N-1) 列只有 1 个元素。您会看到方案，元素数量和列（zero-based 索引）的总和始终为 (N-1).

我不会写这个函数，因为它很复杂，老实说，它对理解没有多大帮助。只需知道从矩阵索引转换为向量是“相当容易的”。

相反的更棘手 CPU-intensive，它应该使用 (N-1) 元素向量来存储向量中每一列的开始位置，以大大加快该过程。谢谢，这个向量也可以（从头到尾）用于“上面”的分区，所以它不会消耗太多内存。

现在，您可以正常对“向量”进行排序，只需将两个双射与向量索引链接在一起，您就会得到一个矩阵单元格。只要排序算法是 stable（通常是这种情况），它就会工作并将您的矩阵“就地”排序，代价是大量数学计算将线性索引“路由”到矩阵索引。

请注意，尽管我们谈论双射，但我们只需要“向量到矩阵”公式。 “矩阵到向量”很重要——它必须是双射！ - 但您不会使用它们，因为您将直接对从 0 到 N²-1.

的（虚拟）向量进行排序

相对于主对角线对二维数组进行排序

Ordering a two-dimensional array relative to the main diagonal

python

sorting

algorithm

multidimensional-array

关于优化的要素：