c# - 我的合并排序代码有什么问题？

Question

我正在学习编码，虽然我会尝试编写合并排序算法(我们在分析类(class)中听说过但不是家庭作业)。我正在根据培训师向我们展示的伪代码工作，但我无法确定问题所在。有人能给我指出正确的方向吗？

编辑:算法只返回列表中的第一个值。

static List<int> mergeSort(List<int> mj)
{
    List<int>m = mj;
    if(m.Count <= 1)
        return m;
    List<int> merge = new List<int>();

    List<int> left = new List<int>();
    List<int> right = new List<int>();
    int middle = m.Count/2;

    for (int i = 0; i < middle; i++)
        left.Add(m[i]);
    for (int j = middle; j >= m.Count; j++)
        right.Add(m[j]);

    left = mergeSort(left);
    right = mergeSort(right);

    merge.AddRange(left);
    merge.AddRange(right);

    for (int k = 0; k < merge.Count; k++)
    {
        Console.Write(merge[k] + ",");
    }
    return merge;

}

Answer 1

您的代码的问题(除了 Mike Cowan 提到的错误)是您没有执行任何实际排序。您首先递归地将列表分成两半(这是正确的)，但随后您只是将它们按原来的顺序连接在一起，因此没有结果:

merge.AddRange(left);
merge.AddRange(right);

您需要做的是遍历您的两个子列表(根据归纳法，它们应该在递归调用中分别排序)，然后按顺序将元素添加到合并列表中。

我们从比较第 0 个元素开始:left[0]反对right[0] .两者中较小者添加到 merge 中列表，其子列表的计数器增加。假设left[0] < right[0] : 我们添加 left[0]至 merge ，在下一次迭代中，我们需要考虑 left[1]反对right[0] .如果left[1]再次变小，我们将它添加到 merge并且，在下一次迭代中，考虑 left[2]反对right[0] .如果right[0]现在是两者中较小的一个，我们将 它 添加到 merge并且，在下一次迭代中，比较 left[2]反对right[1] .等等。

这一直持续到一个子列表用完为止。当发生这种情况时，我们只需将剩余子列表中的所有元素添加到 merge 中即可。 .

int leftIndex = 0;        
int rightIndex = 0;

while (leftIndex < left.Count && rightIndex < right.Count)
    if (left[leftIndex] < right[rightIndex])
        merge.Add(left[leftIndex++]);
    else
        merge.Add(right[rightIndex++]);

while (leftIndex < left.Count)
    merge.Add(left[leftIndex++]);
while (rightIndex < right.Count)
    merge.Add(right[rightIndex++]);

此外，您不应该在您的递归方法中写入控制台。移动你的Console.Write调用您的 Main方法:

static void Main(string[] args)
{
    List<int> original = new List<int>(new int[] { 4, 75, 12, 65, 2, 71, 56, 33, 78,1, 4, 56, 85, 12, 5,77, 32, 5 });
    List<int> sorted = mergeSort(original);

    for (int k = 0; k < sorted.Count; k++)
        Console.Write(sorted[k] + ",");
}