伊莉討論區

標題: 非遞迴Merge Sort [打印本頁]
作者: nemm08    時間: 2013-4-12 02:57 PM     標題: 非遞迴Merge Sort

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

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

}

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

作者: g78312824123    時間: 2013-4-12 06:13 PM

以下不是code喔~~
  1. Function mergeSort(Type data[1..n])
  2.     If n <= 1 then return

  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))

  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]

  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

  29.             While p <= x do
  30.                 data[r] = left[p]
  31.                 p = p + 1
  32.                 r = r + 1

  34.             While q <= y do
  35.                 data[r] = right[q]
  36.                 q = q + 1
  37.                 r = r + 1
  38. End
複製代碼
作者: nemm08    時間: 2013-4-13 12:24 AM

g78312824123 發表於 2013-4-12 06:13 PM
以下不是code喔~~

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



歡迎光臨 伊莉討論區 (http://a401.file-static.com/) Powered by Discuz!