从 C 到 C# 的递归 MergeSort 转换

Question

由于 .NET 要求所有变量在使用前必须首先实例化，因此我完全坚持合并排序的这种递归实现。我的教授希望我们使用递归算法将 MergeSort 的 C 代码翻译成 C#。这是 C 代码：

void doMergeSort(contact **head)
{
    // do not process empty or single-node list
    if (head==NULL || *head == NULL || (*head)->next==NULL)
        return;

    contact *first, *second;

    // split the list in half
    splitList(*head, &first, &second);

    // perform recursive merge sort on both halves
    doMergeSort(&first);
    doMergeSort(&second);

    // Merge both halves back together,
    mergeList(first, second)
}

这是我的实现：

public static void DoMergeSort(ref LinkNode<T> head)
{
    if (head == null || head.Next == null)
        return;

    LinkNode<T> first = null, second = null;

    SplitList(head, ref first, ref second);

    DoMergeSort(ref first);
    DoMergeSort(ref second);

    head = MergeLists(first, second);
}

现在，由于 C#/.NET 的规则，我不能省略实例化 first 和 second，但是在函数中将它们声明为 null 会破坏它的递归性质。我已经被这个问题困扰了好几天，而我的教授却帮不上什么忙。我最好尝试将其转换为迭代函数，还是有一种方法可以递归完成此操作？

我对采用迭代方法的唯一担心是它会 "break the rules" 作业。

Answer 1

我可能遗漏了一些关于 C# 的东西，但是设置 first 和 second = null 应该不是问题，因为 SplitList(...) 应该将列表从头部（不为空）分成两半，上半场进入左边，下半场进入第二场。然后递归发生在现在非空的 first 和 second 列表中，并且每个递归级别都会创建另一对 first 和 second。

该代码并不完全遵循 C 代码，您需要检查列表是否只有一个节点（C 代码检查 (*head)->next == NULL 来执行此操作）。如果只有一个节点，函数应该只是 return.

虽然不是您的 class 作业的一部分，但有一个迭代版本的链表合并排序。它使用一个小的（26 到 32 个）内部列表数组。它比递归版本更快，因为它不必扫描子列表来拆分它们。维基文章对此进行了描述。

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

从 C 到 C# 的递归 MergeSort 转换

Recursive MergeSort translation from C to C#

.net

c#

sorting

mergesort