C#中的MergeSort实现

Question

目前正在研究算法分析,而不是盲目地从我的教科书中运行伪代码,而是在C#中实现每个算法.这是伪代码:

MERGE-SORT(A,p,r)
1  if p < r
2     q = (p+r)/2
3     MERGE-SORT(A,p,q)
4     MERGE-SORT(A,q+1,r)
5     MERGE(A,p,q,r)

MERGE(A,p,q,r)
1  n1 = q - p + 1
2  n2 = r - q
3  let L[1..n1+1] and R[1..n2+1] be new arrays
4  for i = 1 to n1
5     L[i] = A[p+i-1]
6  for j = 1 to n2
7     R[j] = A[q+j]
8  L[n1+1] = INF
9  R[n1+1] = INF
10 i = 1
11 j = 1
12 for k = p to r
13    if L[i] <= R[j]
14       A[k] = L[i]
15       i = i + 1
16    else
17       A[k] = R[j]
18       j = j + 1

这是我的代码:

static void Main(string[] args)
{
    int[] unsortedArray = new int[] { 5, 2, 7, 4, 1, 6, 8, 3, 9, 10 };
    MergeSort(ref unsortedArray, 1, unsortedArray.Length);
    foreach (int element in unsortedArray)
    {
        Console.WriteLine(element);
    }
    Console.Read();
}

private static void MergeSort(ref int[] unsortedArray, int leftIndex, int rightIndex)
{
    if (leftIndex < rightIndex)
    {
        int middleIndex = (leftIndex + rightIndex) / 2;
        //Sort left (will call Merge to produce a fully sorted left array)
        MergeSort(ref unsortedArray, leftIndex, middleIndex);
        //Sort right (will call Merge to produce a fully sorted right array)
        MergeSort(ref unsortedArray, middleIndex + 1, rightIndex);
        //Merge the sorted left & right to finish off.
        Merge(ref unsortedArray, leftIndex, middleIndex, rightIndex);
    }
}

private static void Merge(ref int[] unsortedArray, int leftIndex, int middleIndex, int rightIndex)
{
    int lengthLeft = middleIndex - leftIndex + 1;
    int lengthRight = rightIndex - middleIndex;
    int[] leftArray = new int[lengthLeft + 1];
    int[] rightArray = new int[lengthRight + 1];
    for (int i = 0; i < lengthLeft; i++)
    {
        leftArray[i] = unsortedArray[leftIndex + i - 1];
    }
    for (int j = 0; j < lengthRight; j++)
    {
        rightArray[j] = unsortedArray[middleIndex + j];
    }
    leftArray[lengthLeft] = Int32.MaxValue;
    rightArray[lengthRight] = Int32.MaxValue;
    int iIndex = 0;
    int jIndex = 0;
    for (int k = leftIndex; k < rightIndex; k++)
    {
        if (leftArray[iIndex] <= rightArray[jIndex])
        {
            unsortedArray[k] = leftArray[iIndex];
            iIndex++;
        }
        else
        {
            unsortedArray[k] = rightArray[jIndex];
            jIndex++;
        }
    }
}

我不确定我在哪里弄乱 - 我尽可能地遵循伪代码,但我的输出很时髦(即重复的值并没有正确排序).

调试这个并没有帮助我找出问题(递归解决方案变得太乱).

我哪里出错了,我该如何解决？

Answer 1

正如评论中正确指出的那样,C#数组索引是从零开始的,而您的伪代码是从一开始的.

话虽这么说,这是错误:

1)主要方法

MergeSort(ref unsortedArray, 1, unsortedArray.Length);

必须改为:

MergeSort(ref unsortedArray, 0, unsortedArray.Length - 1);

2)合并方法

leftArray[i] = unsortedArray[leftIndex + i - 1];

必须改为:

leftArray[i] = unsortedArray[leftIndex + i];

3)合并方法

rightArray[j] = unsortedArray[middleIndex + j];

必须改为:

rightArray[j] = unsortedArray[middleIndex + j + 1];

4)合并方法

for (int k = leftIndex; k < rightIndex; k++)

必须改为:

for (int k = leftIndex; k <= rightIndex; k++)

顺便说一句,ref你的代码中的关键字并不是真的必需,因为你只是修改数组中的值而不是创建它的新实例.