时间戳

首页 > 解决方案 > 如何在我的递归快速排序算法中防止堆栈溢出

c# - 如何在我的递归快速排序算法中防止堆栈溢出

问题描述

处理大小超过 5000 的双向链表时，出现堆栈溢出错误。我的算法在每次递归后创建双向链表的 2 个新对象，这些对象在每次递归后附加到排序列表中。是否有另一种创建对象的方法，这样我就不必在快速排序的每次递归中都这样做？

static void quick_sort(List sortList, Node first, Node last)
        {
            //Quick sort algorithm
            Node left, pivNode;
            List bigList = new List();
            List endList = new List();
            int pivot;              
            pivNode = first;        //Sets node to become pivot (1st node in given range)
            left = first.next;      //Sets comparison node
            pivot = first.data;     //Sets integer for pivot

            if (last.next != null)
            {
                //Creates a new list if there are nodes after last node
                endList.firstNode = last.next;
                last.next = null;
                endList.firstNode.prev = null;
            }

            if (left != null)
            {
                do
                {
                    if (left.data > pivot)
                    {
                        Node popNode;
                        popNode = left;
                        removeNode(popNode, sortList);           //Removes node larger than pivot from sortList
                        left = pivNode;                         //Resets left node to pivNode
                        if (bigList.firstNode == null)          //Inserts larger node into bigList
                        {
                            insertBeginning(popNode, bigList);
                        }
                        else
                        {
                            popNode.next = popNode.prev = null;
                            insertEnd(popNode, bigList);
                        }
                    }

                    if (left.data <= pivot)
                    {
                        swapNode(left, pivNode);        //Swaps smaller node with pivNode(moves smaller nodes to left of list)
                        pivNode = left;                 //Resets pivNode to correct node
                    }

                    left = left.next;

                } while (left != last.next);            //Iterates until last given node
            }


            if (endList.firstNode != null)
            {
                //If endList exists
                if (bigList.firstNode != null)
                {
                    //If bigList exists
                    appendLists(bigList, endList);  //Appends endList at end of bigList
                }
                else
                {
                    //If bigList doesn't exist, changes it to endList
                    bigList = endList;              
                }
            }

            appendLists(sortList, bigList);         //Appends bigList to end of sortList

            if (endList.firstNode != null)
            {
                last = endList.firstNode.prev;     //Set's correct last node 
            }

            //Recursion until last has been fully sorted
            if (pivNode.prev != first && pivNode != first)
            {
                quick_sort(sortList, first, pivNode.prev);
            }
            if (pivNode != last && first != last)
            {
                quick_sort(sortList, pivNode.next, last);
            }
        }

标签： c#classrecursionquicksortdoubly-linked-list

解决方案

为防止堆栈溢出，创建两个计数器，名称分别为 left_counter 和 right_counter。在分区步骤期间，更新计数器，以便 left_counter = 从 first 到 pivot 或 pivot.prev 的节点数，而 right_counter 是从 pivot 或 pivot.next 到 last 的节点数。比较两个计数器并在对应于较小计数的子列表上使用递归。然后根据排序的部分（通过递归）更新 first = pivot.next 或 last = pivot.prev 并循环回到代码的顶部以继续。

在排序过程中，创建一个循环双向链表可能更简单，这样 first.prev 指向最后一个节点，last.next 指向第一个节点。这将消除在第一个或最后一个节点处或旁边交换节点时必须检查空值。

该代码显示了使用名为 List 的类类型，但这通常是 C# 的本机类，具有索引（随机访问）“列表”中的元素的能力，类似于数组。列表类可能应该使用不同的名称，也许，“DLList”表示双向链表。

推荐阅读