0

这是一个奇怪的问题，我已经实现了简单的快速排序如下..

        static void Main(string[] args)
    {
        List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
        List<int> sorted = quicksort(unsorted);
        Console.WriteLine(string.Join(",", sorted));
        Console.ReadKey();
    }

    private static List<T> quicksort<T>(List<T> arr) where T : IComparable<T>
    {
        List<T> loe = new List<T>(), gt = new List<T>();

        if (arr.Count < 2)
            return arr;

        int pivot = arr.Count / 2;
        T pivot_val = arr[pivot];
        arr.RemoveAt(pivot);

        foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
                loe.Add(i);
            else
                gt.Add(i);
        }

        List<T> resultSet = new List<T>();
        resultSet.AddRange(quicksort(loe));

        gt.Add(pivot_val);

        resultSet.AddRange(quicksort(gt));
        return resultSet;
    }

输出为：1,2,3,4,5,6,7,8,9

但是当我在未排序列表中使用任何负数时，会出现 stackoverflow 错误，

例如，如果 List unsorted = new List { 1, 3, 5, 7, 9, 8, 6, 4, 2, -1 }; 现在有一个stackoverflow ..

这是怎么回事？为什么这不起作用？

4

2 回答 2

4

您的算法有错误。考虑最简单的输入列表 { 1, -1 }。让我们逐步了解您的逻辑。

  1. 您首先选择一个枢轴索引 Count / 2，即 1。
  2. arr然后，您从列表中删除索引 1 (-1) 处的枢轴元素。
  3. 接下来，您将arr列表中的每个剩余元素（索引 0 处只有 1）与枢轴进行比较。
  4. 1 大于枢轴 (-1)，因此您将其添加到gt列表中。
  5. 接下来，您对loe列表进行快速排序，该列表为空。该排序返回一个空列表，您将其添加到结果集中。
  6. 然后，您将枢轴值添加到gt列表的末尾，因此gt列表现在看起来像这样：{ 1, -1 }。 请注意，这与您开始时的列表完全相同。
  7. 然后，您尝试对gt列表进行快速排序。由于您使用相同的输入调用快速排序例程，因此会再次发生相同的步骤序列，直到堆栈溢出。

您的逻辑中的错误似乎是您盲目地将枢轴添加到 gt 列表中而不将其与任何内容进行比较。我会把它留给你弄清楚如何使它工作。

编辑添加：我假设这是一个家庭作业，但如果不是，我强烈建议在 .NET 上使用 .NET 的内置Sort()方法List<T>。它已经过高度优化和大量测试，并且很可能会比任何自制的产品表现更好。为什么要重新发明轮子？

于 2011-12-29T18:43:41.007 回答
0

如果你没有调试器试试这个...

foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
            {

                loe.Add(i);
                Console.WriteLine("loe.add " + i.ToString());
            }
            else
            {
                gt.Add(i);
                Console.WriteLine("gt.add " + i.ToString());
            }
        }
于 2011-12-29T18:15:36.310 回答