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

Question

什么信号表示程序说：“好，第一次递归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); 
    } 
} 

Answer 1

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

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

在QuickSort的情况下，递归的基本情况是大小为零或1的列表，它们从不需要排序。如果情况并非如此，那么该数组并不意味着被排序。这就是为什么我们再次调用QuickSort方法两次，使用更小尺寸的数组。

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

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