遞歸Quicksort引發堆棧溢出異常

Question

我已經使用Visual Studio在c＃中編寫了遞歸快速排序算法。奇怪的是，當輸入是將要排序的數字的集合時，它的排列數低於9500，它會給出最好，最差和平均情況下的結果。但是，當輸入大於9500時，會拋出一個堆棧溢出異常。我知道還有另一個問題與我在網站上的問題幾乎相同，但是我也做了遞歸的條件。

---

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(); 
    } 

Answer 1

你做了最壞情況快速排序。該數組已經排序並且您嘗試重新排序。

接下來，你的分區（）的代碼確實看起來怪怪的：

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(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個嵌套調用的遞歸級別。