遞歸如何突破第一次遞歸快速排序調用？

什麼信號表示程序說：「好，第一次遞歸quickSort調用完成;繼續第二次遞歸調用」？遞歸如何突破第一次遞歸快速排序調用？

int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element 

    for (int j = low; j <= high- 1; j++) 
    { 
     if (arr[j] <= pivot) 
     { 
      i++; // increment index of smaller element 
      swap(&arr[i], &arr[j]); 
     } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
     int pi = partition(arr, low, high); 
     quickSort(arr, low, pi - 1); 
     quickSort(arr, pi + 1, high); 
    } 
}

來源

2017-02-11 John

您的實際問題根源於Recursion Stack。

我們先來了解一下Recursion，它基本上構成了一種方法，它不斷調用自己日益小的情況，並且每次都重複相同的非遞歸過程，直到它達到基本情況，停止。

在QuickSort的情況下，遞歸的基本情況是大小爲零或1的列表，它們從不需要排序。如果情況並非如此，那麼該數組並不意味着被排序。這就是爲什麼我們再次調用QuickSort方法兩次，使用更小尺寸的數組。

我們在包含A[0] to A[i - 2]的所有元素以及包含元素A[i] to A[A.length - 1]的數組的一側的數組一側遞歸。

爲什麼我們會漏掉A[i - 1]？簡單 - 它已經在它的正確位置。

來源

2017-02-12 00:05:28

好的。我是這樣理解的：一旦你達到了沒有做出另一個遞歸調用的地步，那麼它就會將執行返回到**原始**調用函數。因爲它在原來的調用者中，所以它繼續經過第一次quickSort遞歸調用並進入第二次調用。那是對的嗎？ – John

@AllenEricsson是的。調用恰好是遞歸的並不重要，因爲它與兩個'printf'語句的工作方式相同。當第一個呼叫完成時，第二個呼叫被呼叫。這發生在所有的深度，但這與迭代中的一個無關。 – Sylwester

那麼其他堆棧幀會發生什麼？假設有五個遞歸調用，第五個調用是當low> = high時。其他四幀會發生什麼？ – John

遞歸如何突破第一次遞歸快速排序調用？

回答

相關問題