另一个快速排序计算器 [英] Another Quicksort stackoverflow

问题描述

所以我一直在尝试自己实现快速排序，只是为了从中学习一些东西，但它也产生了一个stackoverflowexception，但我似乎无法找到原因.

So I've been trying to implement a quicksort myself, just to learn something from it, but it also generates a stackoverflowexception, but I can't seem to find what the cause is.

谁能给我一个线索?

  public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser)
        {
            lesser = new List<int>();  // <-- Stackoverflow exception here!
            greater = new List<int>();

            if (valuelist.Count <= 1)
                return;

            pivot = valuelist.First();

            foreach (int Element in valuelist)
            {
                if (Element <= pivot)
                    lesser.Add(Element);
                else
                    greater.Add(Element);
            }
        }

        public List<int> DoQuickSort(List<int> list)
        {
            List<int> great;
            List<int> less;

            Partition(list, out great, out less);

            DoQuickSort(great);
            DoQuickSort(less);

            list.Clear();
            list = (List<int>)less.Concat(great);

            return list;

        }

推荐答案

您没有对 DoQuicksort 的递归调用设置任何条件，因此它永远不会停止递归，从而导致堆栈溢出.如果列表包含多个元素，您应该只在列表上调用 DoQuicksort.

You're not putting any conditions on your recursive calls to DoQuicksort, so it'll never stop recursing, leading to a stack overflow. You should only be calling DoQuicksort on a list if it contains more than one element.

正如 Will 在他的评论中所说，这是快速排序"的一种非常缓慢的方法.您应该查看就地分区算法，如维基百科的快速排序文章所述.

As Will said in his comment, this is a very slow approach to "Quicksort". You should look at in-place partitioning algorithms, as mentioned on Wikipedia's Quicksort article.

这篇关于另一个快速排序计算器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！