c++ - 了解快速排序期间的递归

Question

我是 C++ 的新手，正在学习 http://geeksquiz.com/quick-sort/ 中的一种快速排序算法

这是我无法理解的代码片段，为什么 low 和 high 的值会发生变化

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 current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

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

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

请帮我理解上面的逻辑。

Answer 1

找到一个分区。 partition的发布条件|是枢轴元素左侧的所有内容都将小于或等于分区处的元素，而枢轴元素右侧的所有内容都将大于或等于枢轴元素。递归左右子数组。

通过循环不变式，您将得到一个排序数组。

---

为了简单起见，假设您的分区总是返回中间元素。

你知道partition的后置条件确保 left 至多是 pivot 元素，right 至少是 pivot 元素。

您现在通过使用 low == low 递归调用快速排序对左侧进行递归排序和 high == pi - 1 . pi在正确的空间中，因此您无需担心。最后，您使用 low == pi+1 在右侧数组上调用快速排序。和 high == high .

重复直到所有内容都排序(即 !(low < high) )。

递归任务在此图中得到了很好的解释(我们假设 pivot 每次都是中间元素)。这也方便地显示了平均情况 O(n log n)时间复杂度。