c# - MergeSort() 实现返回初始未排序数组

Question

每次我运行它时，它都会返回一个未排序的数组。我已经放置了一些代码来告诉我事情在哪里发生和没有发生，但看起来一切正常，但它实际上不会对任何事情进行排序。

 public static int[] MergeSort(int[] array)
    {
        if(array.Length <= 1)
        {
            return array;
        }
        (int[], int[]) p = SplitArray(array);
        int[] left = MergeSort(p.Item1);
        int[] right = MergeSort(p.Item2);
        return Merge(left, right);


    }



    public static int[] Merge(int[] low, int[] high)
    {
        int[] middle = new int[(low.Length + high.Length + 1)];
        int count = 0;
        foreach (int item in low)
        {
            Console.WriteLine("low: " + item + ',');
        }
        foreach (int item in high)
        {
            Console.WriteLine("high: " + item + ',');
        }
        int low_index = 0;
        int high_index = 0;
        while (low_index < low.Length && high_index < high.Length)
        {
            if(low[low_index] < high[high_index])
            {
                middle.SetValue(low[low_index], count);
                low_index++;
                count++;
                Console.WriteLine("Low inserted.");
            }
            else
            {
                middle.SetValue(high[high_index], count);
                high_index++;
                count++;
                Console.WriteLine("High inserted.");
            }

        }
        if (low_index == low.Length)
        {
            high.CopyTo(middle, high_index);
        }
        else
        {
            low.CopyTo(middle, low_index);
        }

        return middle;
    }


    public static (int[], int[]) SplitArray(int[] k)
    {
        int MAXINDEX = k.Length - 1;
        int count = 0;
        int[] a = new int[(MAXINDEX / 2)];
        int[] b = new int[(MAXINDEX / 2)];

        for (int i = 0; i < (MAXINDEX / 2); i++)
        {
            a[i] = k[i];
        }
        for (int i = ((MAXINDEX / 2) + 1); i < MAXINDEX; i++)
        {
            b[count] = k[i];
            count++;

        }
        return (a, b);

    }

我不知道我哪里错了。每次回到这里，我可能只是因为非常疲倦而忽略了一些事情。我基本上打印了一堆应该使用控制台发生的事情，这一切似乎都是正确的，我正在失去理智。

标签： c#mergesort

Answer 1

好的，我认为主要错误是 high.copyTo(...) 和 low.copyTo(...) 的函数索引错误

这里是完整的源代码（经过测试）：

public static int[] MergeSort(int[] array)
{
  if (array.Length <= 1)
  {
    return array;
  }

  Tuple<int[], int[]> p = SplitArray(array);

  int[] left = MergeSort(p.Item1);
  int[] right = MergeSort(p.Item2);

  return Merge(left, right);
}

public static int[] Merge(int[] low, int[] high)
{
  int[] middle = new int[low.Length + high.Length];
  int count = 0;
  foreach (int item in low)
  {
    Console.WriteLine("low: " + item + ',');
  }
  foreach (int item in high)
  {
    Console.WriteLine("high: " + item + ',');
  }
  int low_index = 0;
  int high_index = 0;
  while (low_index < low.Length && high_index < high.Length)
  {
    if (low[low_index] < high[high_index])
    {
      middle[count] = low[low_index];
      low_index++;
      count++;
      Console.WriteLine("Low inserted.");
    }
    else
    {
      middle[count] = high[high_index];
      high_index++;
      count++;
      Console.WriteLine("High inserted.");
    }

  }
  if (low_index == low.Length)
  {
    for (; count < middle.Length; count++)
    {
      middle[count] = high[high_index];
      high_index++;
    }

    // alternate: Array.Copy(high, high_index, middle, count, middle.Length - count);
  }
  else
  {
    for (; count < middle.Length; count++)
    {
      middle[count] = low[low_index];
      low_index++;
    }
    // alternate: Array.Copy(low, low_index, middle, count, middle.Length - count);
  }

  return middle;
}

public static Tuple<int[], int[]> SplitArray(int[] k)
{
  int half = k.Length / 2;
  int[] a = new int[half];
  int[] b = new int[k.Length - half];

  int k_index = 0;

  for (int i = 0; i < a.Length; i++)
  {
    a[i] = k[k_index];
    k_index++;
  }

  for (int i = 0; i < b.Length; i++)
  {
    b[i] = k[k_index];
    k_index++;
  }

  return new Tuple<int[], int[]>(a, b);
}