非遞迴Merge Sort

nemm08

最近有一份作業 要用stack 寫 非遞迴Merge Sort 加上 Comparator

public static <T> void mergeSort(T[] arr, Comparator<? super T> comp){

}

不知道如何開始: 有人可以給pseudocode ? 或解釋一下我該如何開始

g78312824123

以下不是code喔~~

1. Function mergeSort(Type data[1..n])
   
2.     If n <= 1 then return
   
3. 
   
4.     Index i, j, k
   
5.     For i from 2 to (n / 2) do
   
6.         For j from 0 to (n - 1) step (2 * i) do
   
7.             Index x, y
   
8.             x = min(i, n - j)
   
9.             y = min(i, max(0, n - i - j))
   
10. 
    
11.             Type left[1..x], right[1..y]
    
12.             For k from 1 to x do
    
13.                 left[k] = data[j + k]
    
14.             For k from 1 to y do
    
15.                 right[k] = data[i + j + k]
    
16. 
    
17.             Index p, q, r
    
18.             p = q = 1
    
19.             r = j
    
20.             While p <= x and q <= y do
    
21.                 If left[p] < right[q] then
    
22.                     data[r] = left[p]
    
23.                     p = p + 1
    
24.                 Else
    
25.                     data[r] = right[q]
    
26.                     q = q + 1
    
27.                 r = r + 1
    
28. 
    
29.             While p <= x do
    
30.                 data[r] = left[p]
    
31.                 p = p + 1
    
32.                 r = r + 1
    
33. 
    
34.             While q <= y do
    
35.                 data[r] = right[q]
    
36.                 q = q + 1
    
37.                 r = r + 1
    
38. End

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

nemm08

g78312824123 發表於 2013-4-12 06:13 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

以下不是code喔~~

我已經學會了 但還是感恩!