二維數組的排序

-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

二維數組的排序

回答

相關問題