1

我正在尝试使用 Wolfram Mathematica 创建一个合并排序，但我仍然遇到这个递归错误，我不知道我在哪里犯了错误。我从 Java 重写了这段代码，它工作得很好，所以我想这对 Wolfram 来说是一些特别的事情。你有什么想法，我的代码有什么问题吗？

非常感谢！

Heer 是我的代码：

mergeSort[x_, left_, right_] := 
 Module[{array = x, middle, n1, n2, L, R, i, j, k}, 
  If[left < right,
    middle = (left + right) / 2;
    
    mergeSort[array, left, middle];
    mergeSort[array, middle + 1, right];
    
    n1 = middle - left + 1;
    n2 = right - middle;
    
    L = {};
    R = {};
    
    For[i = 1, i < n1, ++i,
     L[[i]] = array[[left + 1]];
     ];
    For[j = 1, j < n2, ++j,
     R[[j]] = array[[middle + 1 + j]];
     ];
    
    i = 0;
    j = 0;
    k = left;
    
    While[i < n1 && j < n2,
     If[L[[i]] <= R[[j]],
      array[[k]] = L[[i]];
      i++;
      ,
      array[[k]] = R[[j]];
      j++;
      ];
     k++;
     ];
    
    While[i < n1, 
     array[[k]] = L[[i]];
     i++;
     k++;
     ];
    
    While[j < n2,
     array[[k]] = R[[j]];
     j++;
     k++;
     ];
    Return[array];
    ];
  ]

这是我的函数调用-mergeSort[{58, 3, 98}, 0, 3];

4

1 回答 1

0

您的代码中有三个主要问题。

  1. 您尝试调整的 GfG 代码arr通过引用传递数组，因此每个递归都在同一个对象上操作。这在 Mathematica 中通常不会发生。我已添加通过引用HoldFirst传递。另一种选择是简单地完全忽略函数调用并将其直接修改为全局变量。例如array array

    mergeSort[left_, right_] := Module[{},
  If[left < right,
   middle = Floor[(left + right)/2];
   mergeSort[left, middle];
   mergeSort[middle + 1, right];
   ...

  2. GfG 代码执行int m = (l + r) / 2的结果被四舍五入。这需要在 Mathematica 中明确完成：middle = Floor[(left + right)/2]. 否则你会得到无限递归。

  3. GfG 代码使用从零开始的数组。Mathematica 使用基于 1 的列表，因此for (int i = 0; i < n1; ++i)可以将代码更改为For[i = 1, i <= n1, ++i, ...

您在 GfG 代码中的这一行中也有一个错字：L[i] = arr[l + i]，最后您不需要Return在 Mathematica 中使用来在函数末尾返回值。

Attributes[mergeSort] = HoldFirst;

mergeSort[array_Symbol, left_Integer, right_Integer] :=
 Module[{middle, n1, n2, L, R, i, j, k},
  If[left < right,
   middle = Floor[(left + right)/2];

   mergeSort[array, left, middle];
   mergeSort[array, middle + 1, right];

   n1 = middle - left + 1;
   n2 = right - middle;

   L = ConstantArray[Null, n1];
   R = ConstantArray[Null, n2];

   For[i = 1, i <= n1, ++i,
    L[[i]] = array[[left + i - 1]];
    ];
   For[j = 1, j <= n2, ++j,
    R[[j]] = array[[middle + j]];
    ];

   i = 1;
   j = 1;
   k = left;

   While[i <= n1 && j <= n2,
    If[L[[i]] <= R[[j]],
     array[[k]] = L[[i]];
     i++;
     ,
     array[[k]] = R[[j]];
     j++;
     ];
    k++;
    ];

   While[i <= n1,
    array[[k]] = L[[i]];
    i++;
    k++;
    ];

   While[j <= n2,
    array[[k]] = R[[j]];
    j++;
    k++;
    ];
   array
   ]
  ]

array = {58, 3, 98};

mergeSort[array, 1, Length[array]]

{3, 58, 98}

请注意，这已更改array.

array

{3, 58, 98}

替代版本

Mathematica 成语中更多的版本是由Wellin、Gaylord 和 Kamin 编写的。

merge[lis_List, {}] := lis
merge[{}, lis_List] := lis

merge[{a_, ra___}, {b_, rb___}] :=
 If[a <= b,
  Join[{a}, merge[{b}, {ra, rb}]],
  Join[{b}, merge[{a, ra}, {rb}]]]

MergeSort[{}] := {}
MergeSort[{x_}] := {x}
MergeSort[lis_List] := Module[{div = Floor[Length[lis]/2]},
  merge[MergeSort[Take[lis, div]], MergeSort[Drop[lis, div]]]]

MergeSort[{58, 3, 98}]

{3, 58, 98}

于 2020-10-06T12:38:29.837 回答