程序仍然处于无限递归中

Question

我正试图使用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];

Answer 1

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

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使用基于一的列表，因此for (int i = 0; i < n1; ++i)等代码可以更改为For[i = 1, i <= n1, ++i, ...

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

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&卡明。

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｝