了解快速排序期间的递归

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

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

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

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

你知道 partition 的 post 条件确保左边最多是枢轴元素，右边至少是枢轴元素。

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

在右侧数组上调用快速排序

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

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

Answer 2

你已经澄清了你的问题，你理解 partition() 背后的逻辑，但不理解递归。好的

您必须先假设 quickSort() 将对您的数组进行排序。接受它作为给定的。一个公理。这一定是真的。您确信 quickSort() 会对您的数组进行排序。你必须接受这个声明作为一个无可置疑的真理，作为一个起点。

那么，你已经明白partition()把列表分成两半了。基于此，您可以得出以下结论：

枢轴元素之前的数组的一半仅包含小于枢轴元素的值。
枢轴元素后的数组的一半仅包含大于枢轴元素的值。
1 & 2 是 partition() 操作的结果，你说你完全理解。给定 1 和 2 作为起点，然后您可以得出结论，如果 1 和 2 中引用的数组的一半本身已完全排序，那么整个数组将必须完全排序。
如何使 1 和 2 为真？那么，您递归地应用 quickSort() 算法。您刚刚同意 quickSort() 将对它获得的数组进行完全排序。所以，quickSort()对两半进行递归排序后，最终结果一定是完全排序的列表。

Q.E.D.

P.S。上面使用的术语 "half of the array" 是一个使用不严格的术语。当然，每一半数组的实际大小不会恰好是原始数组的一半。这对整体逻辑没有影响。

了解快速排序期间的递归

Understanding recursion during QuickSort

c++

algorithm

quicksort