C#中的自顶向下合并排序实现

Question

我正在尝试按照 Wikipedia 中所述在 C# 中实现自上而下的合并排序算法。下面的实现是我想出的，但是，它似乎没有正确排序数组。我已经调试了几次，但无法弄清楚代码哪里出错了。任何帮助将不胜感激。

using System;

class MergeSort
{
    static void Main()
    {
        int[] A = { 4, 3, 2, 1 };
        int lastIndex = A.Length - 1;
        int[] B = new int[A.Length];
        Array.Copy(A, B, A.Length);
        MergeSortNumbers(B, 0, lastIndex, A);
        foreach (var item in A)
        {
            Console.WriteLine("{0} ", item);
        }
    }

    private static void MergeSortNumbers(int[] B, int iStart, int iEnd, int[] A)
    {
        int iMiddle = (iStart + iEnd) / 2;
        if ((iEnd - iStart) < 2)
        {
            // Merge(B, iStart, iMiddle, iEnd, A);
            return;
        }
        MergeSortNumbers(A, iStart, iMiddle - 1, B);
        MergeSortNumbers(A, iMiddle, iEnd, B);
        Merge(B, iStart, iMiddle, iEnd, A);
    }

    private static void Merge(int[] A, int iStart, int iMiddle, int iEnd, int[] B)
    {
        int i = iStart;
        int j = iMiddle;

        for (int k = iStart; k < iEnd; k++)
        {
            if (i < iMiddle && (j >= iEnd || A[i] <= A[j]))
            {
                B[k] = A[i];
                i = i + 1;
            }
            else
            {
                B[k] = A[j];
                j = j + 1;
            }
        }
    }
}

Answer 1

有两个问题。你应该知道 iEnd 是独占的。这意味着 iEnd 它自己不考虑索引。这是因为 Merge 方法中的 j >= iEnd 条件和 MergeSortNumbers 方法中的 (iEnd - iStart) < 2。

iMiddle 也专用于左侧。因为 Merge 方法中的 i < iMiddle 条件。

所以基本上不要将 ends 减 1。（如果 ends 包含在内，你只减一）

static void Main()
{
    int[] A = { 4, 3, 2, 1 };
    int[] B = new int[A.Length];
    Array.Copy(A, B, A.Length);
    MergeSortNumbers(B, 0, A.Length, A); // Do not decrement A.Length
    foreach (var item in A)
    {
        Console.WriteLine("{0} ", item);
    }
}

private static void MergeSortNumbers(int[] B, int iStart, int iEnd, int[] A)
{
    if ((iEnd - iStart) < 2) return;

    int iMiddle = (iStart + iEnd) / 2;
    MergeSortNumbers(A, iStart, iMiddle, B); // Do Not decrement iMiddle
    MergeSortNumbers(A, iMiddle, iEnd, B);
    Merge(B, iStart, iMiddle, iEnd, A);
}

private static void Merge(int[] A, int iStart, int iMiddle, int iEnd, int[] B)
{
    int i = iStart;
    int j = iMiddle;

    for (int k = iStart; k < iEnd; k++)
    {
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j]))
        {
            B[k] = A[i++];
        }
        else
        {
            B[k] = A[j++];
        }
    }
}

C#中的自顶向下合并排序实现

Top-down Merge Sort implementation in C#

c#

sorting

mergesort