是否总是可以在所有维度上订购多维数组？怎么样？

Question

假设,我有一个n整数数组(因为n=1它是一个矢量,因为n=2它是一个矩形矩阵,因为n=3它是一个平行六面体等).我需要重新排序数组的元素,以便每行,列等中的元素处于非递减顺序.

• 是否可以输入任何数组？
• 所需的排序是否对任何输入数组都是唯一的？我刚刚意识到这个问题的答案一般是否定的,例如对于方形矩阵.
• 对于在所有维度上具有不同长度的任何输入数组,所需的排序是唯一的吗？
• 生成所需订购的最快算法是什么？

Answer 1

任何输入数组都可以吗？

是的，如果我们将数组视为具有相同数量元素的单维数组，然后通过将其遍历回原始 n 维数组来对其进行排序，那么它仍然是排序的，因为对于每个：对于i1,....,i_k,...,i_m所有i_k < i_k'：

i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...
Thus (the array is ordered):
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...]
Thus (back to original array):
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...

至于第二个问题：

对于所有维度上具有不同长度的输入数组，所需的排序是否唯一？

不：

1 1          1 3
3 4          1 4
5 6          5 6

产生所需排序的最快算法是什么？

已经建议了一种解决方案：将其视为一个大的长数组并对其进行排序。复杂性是O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
我的直觉，如果你能做得更快，那么你可以更快O(nlogn)，但我没有证据证明这个说法，所以它可能是错误的。