IComparable< T>当用于负数时给出stackoverflow

本文关键字：stackoverflow 用于 IComparable | 更新日期: 2023-09-27 18:19:06

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

        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.

怎么回事?

IComparable< T>当用于负数时给出stackoverflow

你的算法有bug。考虑最简单的输入列表{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列表中，而不将其与任何内容进行比较。我把如何使它工作留给你去想办法。

编辑补充:我假设这是一个家庭作业，但如果不是，我强烈建议在List<T>上使用。net内置的Sort()方法。它经过了高度优化和大量测试，很可能比任何自酿的都要好。为什么要重新发明轮子?

如果你没有调试器，试试这个…

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());
            }
        }
相关文章：