作为合并排序的第一次尝试,我产生了下面的代码,它适用于字符串,因为它们比列表更容易处理。
class Program
{
static int iterations = 0;
static void Main(string[] args)
{
string test = "zvutsrqponmlihgfedcba";
test = MergeSort(test);
// test is sorted after 41 iterations
}
static string MergeSort(string input)
{
iterations++;
if (input.Length < 2)
return input;
int pivot = 0;
foreach (char c in input)
pivot += c;
pivot /= input.Length;
string left = "";
string right = "";
foreach (char c in input)
if (c <= (char)pivot)
left += c;
else
right += c;
return string.Concat(new string[] { MergeSort(left), MergeSort(right) });
}
}
阅读维基百科上关于可能的优化,我发现以下提示"为了确保最多O(log N)空间被使用,首先递归到数组的较小一半,并使用尾部调用递归到另一半。"但老实说,我不知道如何将此应用于我的情况。我隐约记得IT课上的尾调用,当时我们在学习递归和阶乘,但我真的不明白如何将维基百科的建议应用到我的代码中。
这个问题有很多问题,首先你已经实现了一个非常慢的快速排序版本,但问了一个关于合并排序的问题。合并排序通常不是作为尾部递归算法实现的。
让我代表你问一个更好的问题:
如何把递归算法变成尾递归算法?
让我画出一个更简单的尾递归变换,然后你可以计算出如何将其应用到你的排序中,如果你认为这样做是个好主意的话。
假设您有以下递归算法:
static int Count(Tree tree)
{
if (tree.IsEmpty)
return 0;
return 1 + Count(tree.Left) + Count(tree.Right);
}
让我们使用以下有点奇怪的转换将其分解成更多的步骤:
static int Count(Tree tree)
{
int total = 0;
Tree current = tree;
if (current.IsEmpty)
return 0;
total += 1;
int countLeft = Count(current.Left);
total += countLeft;
current = current.Right;
int countRight = Count(current);
total += countRight;
return total;
}
请注意,这与之前的程序完全相同,只是更加冗长。当然,你不会用这种冗长的方式编写程序,但它将帮助我们使其尾部递归。
尾部递归的目的是将递归调用转换为goto。我们可以这样做:
static int Count(Tree tree)
{
int total = 0;
Tree current = tree;
Restart:
if (current.IsEmpty)
return total;
int countLeft = Count(current.Left);
total += 1;
total += countLeft;
current = current.Right;
goto Restart;
}
看到我们做的了吗?我们没有递归,而是将当前引用重置为将要递归的对象,并返回到开始处,同时保持累加器的状态。
现在很清楚如何对快速排序算法做同样的事情?
这看起来像是快速排序的一个不太理想的变体,而不是合并排序。您缺少了与此部分等价的c#:
function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result