递归快速排序引发堆栈溢出异常

本文关键字：栈溢出 异常 堆栈 快速排序 递归 | 更新日期: 2023-09-27 18:26:59

我使用Visual Studio在c#中编写了一个递归快速排序算法。奇怪的是，当输入（将被排序的数字的集合）在数组中低于9500时，它会给出最佳、较差和可用的结果。然而，当输入大于9500时，它会抛出一个stackerflow异常。我知道还有一个问题和我在网站上的问题几乎一样，但我也做了可以递归的条件。

public int[] quick(int [] myarray,int p,int r)
    {
        int q;
        if (p < r)
        {
            q = partition(myarray, p, r);
            quick(myarray, p, q - 1);
            quick(myarray, q + 1, r);
        }
        return myarray;
    }
    public int partition(int [] myarray, int left, int right)
    {
        int i = left - 1;
        int tmp = 0;
        int pivot = myarray[right];
        for (int j = left; j < right; j++)
        {
            if (myarray[j] < pivot)
            {
                i = i + 1;
                tmp = myarray[i];
                myarray[i] = myarray[j];
                myarray[j] = tmp;
            }
        }
        tmp = myarray[i + 1];
        myarray[i + 1] = myarray[right];
        myarray[right] = tmp;
        return i + 1;
    }
 static void Main(string[] args)
    {
        Stopwatch mwatch = new Stopwatch();
        Program quickprogram = new Program();
        int[] mydizi = new int[9000];
        //int counter = 9000;
        //initialization of quick array
        for (int i = 0; i < mydizi.Length; i++)
        {
            mydizi[i] = i + 1;
        }
       int[] result = new int[9000]; //return array
        //time is starting
        mwatch.Start();
        //algorithm is called
        result = quickprogram.quick(mydizi,0,mydizi.Length-1);
        //result is returned from quickprogram
        for (long j = 0; j < result.Length;j++)
        {
            Console.Write(result[j] + ",");
        }
        mwatch.Stop();
        //time is up
        //Printing the time that show how it takes
        Console.Write("Ms:" + mwatch.Elapsed.Milliseconds + " S:" + mwatch.Elapsed.Seconds + " Mn:" + mwatch.Elapsed.Minutes + " Hr:" + mwatch.Elapsed.Hours);
        Console.ReadLine();
    }

递归快速排序引发堆栈溢出异常

您可以进行最坏情况下的快速排序。数组已排序，您尝试再次对其排序。

接下来，您的partition（）代码看起来确实很奇怪：

int i = left - 1;                   // i = left-1
int pivot = myarray[right];
for (int j = left; j < right; j++)  // j = left
{
    if (myarray[j] < pivot)
    {
        i = i + 1;                  // now i = left-1+1 = left = j
        tmp = myarray[i];
        myarray[i] = myarray[j];
        myarray[j] = tmp;           
        // congratulations!
        // you successfully exchanged a value with itself!
    }

最终结果是，使用以下参数（数组大小为9）递归调用quick（）：

 quick( 0, 8)
> quick( 0, 7)
>> quick( 0, 6)
>>> quick( 0, 5)
>>>> quick( 0, 4)
>>>>> quick( 0, 3)
>>>>>> quick( 0, 2)
>>>>>>> quick( 0, 1)
>>>>>>>> quick( 0, 0)
>>>>>>>> quick( 2, 1)
>>>>>>> quick( 3, 2)
>>>>>> quick( 4, 3)
>>>>> quick( 5, 4)
>>>> quick( 6, 5)
>>> quick( 7, 6)
>> quick( 8, 7)
> quick( 9, 8)

您可以看到，使用9000个元素执行此操作将很容易达到9000个嵌套调用的递归级别。

相关文章：