java - 为什么快速排序需要递归 "sorted"小节？

Question

对算法/数据结构还是很陌生，一直在尝试学习如何应用快速排序。

我发现了以下实现:https://www.geeksforgeeks.org/quick-sort/

让我感到困惑的部分:

/* The main function that implements QuickSort() 
      arr[] --> Array to be sorted, 
      low  --> Starting index, 
      high  --> Ending index */
    void sort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
        /* pi is partitioning index, arr[pi] is  
          now at right place */
        int pi = partition(arr, low, high); 

        // Recursively sort elements before 
        // partition and after partition 
        sort(arr, low, pi-1); 
        sort(arr, pi+1, high); 
    } 
} 

在我看来，我们不应该对 sort(arr, low, pi-1) 部分进行递归，因为算法应该已经对该部分进行了排序......

Answer 1

在您实现快速排序的过程中，我在某些地方进行了注释，以便更清楚地说明快速排序背后的思想。在您使用 partition 函数计算变量 pi 的代码中，索引 pi 之前的所有元素都小于 arr[pi] 但不能保证它们按排序顺序排列。此外，索引 pi 之后的所有元素都大于 arr[pi] 但不能保证这些按顺序排列。我在下面的代码中注释掉了:

int partition (arr[], low, high)
{
   // pivot (Element to be placed at right position)
   pivot = arr[high];  
   i = (low - 1)  // Index of smaller element
   for (j = low; j <= high- 1; j++)
   {
    // If current element is smaller than or equal to pivot
    /* But, it does not guaranteed that smaller elements will come in sorted fashion*/
    if (arr[j] <= pivot)
    {
        i++;    // increment index of smaller element
        swap arr[i] and arr[j]
     }
   }
   swap arr[i + 1] and arr[high])
   return (i + 1)
 }

/* The main function that implements QuickSort() 
  arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
 void sort(int arr[], int low, int high) 
 { 
    if (low < high) 
    { 
    /* pi is partitioning index, arr[pi] is  
      now at right place */
     int pi = partition(arr, low, high); 
     /*Here, all the elements before index pi are less than arr[pi] but 
       not guaranteed that they are in sorted order.
       Also, all the elements after index pi are greater than arr[pi] but 
       not guaranteed to be in sorted order.
     */
     // Recursively sort elements before 
     // partition and after partition 
     sort(arr, low, pi-1); 
     sort(arr, pi+1, high); 
  } 
}