递归QuickSort stackoverflowException [英] Recursive QuickSort stackoverflowexception

问题描述

嗨！我的代码中不断出现StackOverFlowException，但似乎找不到问题.请帮帮我.

Hi! I keep getting StackOverFlowException in my code and I can''t seem to find the problem. Please help me.

class Program
{
    static void Main(string[] args)
    {
        int x = 3;
        List<int> num = new List<int>();
        Random rnd = new Random();
        for (int i = 0; i < x; i++)
        {
            num.Add(rnd.Next(99));
        }
        Sort s = new Sort();
        int q = 1, w = 0;

        s.QuickSort<int>(num);


    }
}

public class Sort
{
    public Sort()
    {
    }
    public void QuickSort<T>(List<T> Tlist) where T : IComparable
    {
        List<T> tmp = QuickSortHelper(Tlist);
        Tlist.Clear();
        foreach (T t in tmp)
            Tlist.Add(t);
    }
    public List<T> QuickSortHelper<T>(List<T> Tlist)  where T : IComparable
    {
        List<T> left= new List<T>(), right = new List<T>(), returList = new List<T>();
        if (Tlist.Count <= 1)
            return Tlist;
        int x =Tlist.Count-1;
        T pivot = Tlist[x];
        foreach (T t in Tlist)
            if (t.CompareTo(pivot) == -1)
                left.Add(t);
            else right.Add(t);
        foreach(T t in QuickSortHelper<T>(left))
            returList.Add(t);
        returList.Add(pivot);
        foreach (T t in QuickSortHelper<T>(right))
            returList.Add(t);
        return returList;
    }

推荐答案

递归程序中的堆栈溢出通常意味着某些终止条件不正确.查看您的代码(我希望不是您的程序的全部)，每次调用QuickSortHelper时，它都会返回一个比其输入大一个元素的列表. (提示:Pivot元素会发生什么?)如果继续这样做，(1)它将永远不会终止，(2)它会耗尽内存.

Stack overflow in recursive programs generally means that some termination condition isn''t right. Looking at your code (which I hope is not all of your program), each time QuickSortHelper is called, it returns a list one element larger than its input. (Hint: what happens to the Pivot element?) If you keep on doing that, (1) it will never terminate and (2) it will run out of memory.

这篇关于递归QuickSort stackoverflowException的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！