递归如何突破第一个递归快速排序调用？

Question

程序要说什么信号，"Ok the first recursive quickSort call is done; proceed to the second recursive call"？

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

Answer 1

您的实际问题根源于 Recursion Stack。

让我们先来了解一下Recursion，它基本上构成了一个方法，它在越来越小的情况下不断调用自己，并且每次都重复相同的非递归过程，直到到达基本情况，然后停止。

在 QuickSort 的情况下，递归的基本情况是大小为零或一的列表，它们永远不需要排序。如果不是这种情况，则数组不应该被排序。这就是为什么我们对较小的数组再次调用 QuickSort 方法两次。

我们递归包含 A[0] to A[i - 2] 中所有元素的数组一侧，以及包含 A[i] to A[A.length - 1].

元素的数组一侧

为什么我们要省略 A[i - 1]？简单 - 它已经在正确的位置。

递归如何突破第一个递归快速排序调用？

How does recursion break out of the first recursive quick sort call?

algorithm

recursion

quicksort