合并排序 - 微小的更改会引发 SystemInvalidOperationException

Question

我的程序中发生了一件非常奇怪的事情。这是简化的代码。

class Program
{
    static void Main(string[] args)
    {
        ArrayList numbers = new ArrayList();
        numbers.Add(1);
        numbers.Add(3);
        numbers.Add(4);
        numbers.Add(2);

        var it = Sorts.MergeSort((ArrayList)numbers.Clone());
        Sorts.PrintArray(it, "mergesort");

        Console.WriteLine("DONE");
        Console.ReadLine();
    }
}

public static class Sorts
{
    public static ArrayList BubbleSort(ArrayList numbers)
    {

        bool sorted = true;
        for (int i = 0; i < numbers.Count; i++)
        {

            for (int j = 1; j < numbers.Count; j++)
            {
                if ((int)numbers[j - 1] > (int)numbers[j])
                {
                    int tmp = (int)numbers[j - 1];
                    numbers[j - 1] = numbers[j];
                    numbers[j] = tmp;
                    sorted = false;
                }
            }
            if (sorted)
            {
                return numbers;
            }
        }
        return numbers;
    }

    public static ArrayList MergeSort(ArrayList numbers, int switchLimit = 3)
    {

        //if I use this if - everything works
        if (numbers.Count <= 1)
        {
           // return numbers;
        }

        //the moment I use this condition - it throws SystemInvalidOperationException in function Merge in the line of a "for"-loop
        if (numbers.Count <=switchLimit)
        {
              return Sorts.BubbleSort(numbers);
        }

        ArrayList ret = new ArrayList();
        int middle = numbers.Count / 2;

        ArrayList L = numbers.GetRange(0, middle);
        ArrayList R = numbers.GetRange(middle, numbers.Count - middle);
        L = MergeSort(L);
        R = MergeSort(R);

        return Merge(L, R);
    }

    private static ArrayList Merge(ArrayList L, ArrayList R)
    {

        ArrayList ret = new ArrayList();

        int l = 0;
        int r = 0;
        for (int i = 0; i < L.Count + R.Count; i++)
        {
            if (l == L.Count)
            {
                ret.Add(R[r++]);

            }
            else if (r == R.Count)
            {
                ret.Add(L[l++]);
            }

            else if ((int)L[l] < (int)R[r])
            {
                ret.Add(L[l++]);
            }
            else
            {
                ret.Add(R[r++]);
            }
        }

        return ret;
    }

    //---------------------------------------------------------------------------------

    public static void PrintArray(ArrayList arr, string txt = "", int sleep = 0)
    {
        Console.WriteLine("{1}({0}): ", arr.Count, txt);
        for (int i = 0; i < arr.Count; i++)
        {
            Console.WriteLine(arr[i].ToString().PadLeft(10));
        }
        Console.WriteLine();
        System.Threading.Thread.Sleep(sleep);
    }
}

我的 Sorts.MergeSort 函数有问题。 当我正常使用它时（看一下函数中的第一个 if 条件 - 一切都完美。 但是，当我希望它切换到具有较小输入的冒泡排序（函数中的第二个 if 条件）时，它会抛出 SystemInvalidOperationException。我不知道问题出在哪里。 你看到了吗？ 谢谢。 :) 备注：冒泡排序本身是有效的 - 所以这种排序应该不会有问题......

Answer 1

问题在于您使用 GetRange：

此方法不会创建元素的副本。新的 ArrayList 只是源 ArrayList 的一个视图窗口。然而，对源ArrayList的所有后续更改都必须通过此视图窗口ArrayList来完成。如果直接对源 ArrayList 进行更改，则视图窗口 ArrayList 无效，并且对其进行的任何操作都将返回 InvalidOperationException。

您正在原始 ArrayList 上创建两个视图并尝试使用这两个视图 - 但是当一个视图修改基础列表时，另一个视图实际上会失效。

如果您更改代码以创建子列表的副本 - 或者如果您在指定范围内直接使用原始列表 - 那么我相信它会正常工作。

（正如评论中所述，我还强烈建议您使用通用集合。）

这是一个简短但完整的程序，它演示了您遇到的问题：

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        ArrayList list = new ArrayList();
        list.Add("a");
        list.Add("b");

        ArrayList view1 = list.GetRange(0, 1);
        ArrayList view2 = list.GetRange(1, 1);

        view1[0] = "c";
        Console.WriteLine(view2[0]); // Throws an exception
    }
}

Answer 2

在这一行 R = MergeSort(R); 中，您更改了 L 表示的数字范围。这会使 L 无效。抱歉，我必须走了，所以现在无法进一步解释。