二维数组的排序

-1

我正试图解决2D数组上的问题，并且需要一点帮助。问题如下：二维数组的排序

假设我们有一个大小为nxn的二维数组A，其中包含唯一元素。需要重新排列A的元素如下。令A11，A12，A21，A22为A的四个互不相交的子阵列，每个子阵列的大小为n/2×n/2。然后A11 < A12 < A21 < A22。如果这些子阵列中的每一个被递归地分割成四个相同大小的子阵列，那么该属性也成立。

用户输入：n，N（≥n2）。 n是2的幂数

我已经尝试了很多东西，但似乎没有任何工作。

来源

2011-07-30 rits

几乎为http://stackoverflow.com/同样的问题问题/ 6882083 /生成和排序-IN-A-2D阵列/ 6882282＃注释-8190935。仍然有同样的缺陷：你将不得不解释句子“Then A11 whoplisp

你尝试了很多东西？你尝试了什么？这与C有什么关系？你有任何代码向我们展示？或者这应该去math.stackexchange.com？ etc. – Bart

这是一个功课？ – unkulunkulu

您需要创建一个函数，它将根据所讨论的顺序将0和n * n-1之间的索引转换为数组中的坐标。然后，您只需运行一些常用的1D排序算法，在n * n个大小的数组上，使用该函数替换其中的第n个元素。它解决了这个问题。

更新：在这个矩阵的坐标映射函数映射数字：

采取一切值：

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

来源

2011-07-30 13:50:49 unkulunkulu

我想到了这一点，但似乎不明白如何递归执行子数组内的子数组。 – rits

@rits，映射函数可以递归。只需绘制一些映射的例子。 – unkulunkulu

你能帮我一些伪代码 – rits

上unkulunkulu的答案，我想你可以按如下方式接近它有点捎带你的矩阵（2D）并把它们放在一个简单的数组（1D）中。然后取这个数组，并将值从低到高排序。

现在您需要做的是再次填充矩阵，但是要以符合您指定的规则的方式进行。如果你看看Z-order space filling curve in 2D，你会发现如果你按照这个顺序填充你的矩阵（使用排序后的元素），结果矩阵就会具有你想要的属性。

现在实际上编码这将取决于你。

来源

2011-07-30 14:54:01 Bart

书中的数字食谱章节21.8 http://www.nrbook.com/nr3/给出了一个分析表达式来计算给定四叉树坐标的二维数组的索引。

enter image description here

这里是我尝试另一种直接的方法，但我不喜欢它尽可能多：

(defun quad-pos (pos) 
    "POS is a list of letters that indicate the position in a 2x2 matrix [a,b; c,d]." 
    (let ((x 0) 
    (y 0) 
    (s 1)) 
    (dolist (e pos) 
     (setf s (/ s 2)) 
     (ecase e 
    ('a) 
    ('b (incf x s)) 
    ('c (incf y s)) 
    ('d (incf x s) (incf y s)))) 
    (values x y))) 
#+nil 
(quad-pos '(a)) ;=> 0, 0 
#+nil 
(quad-pos '(a b c)) ;=> 1/4, 1/8 
#+nil 
(quad-pos '(d d d d)) ;=> 15/16, 15/16

来源

2011-07-30 15:03:36 whoplisp

二维数组的排序

回答

相关问题