递归在这个快速排序程序中是如何工作的

Question

这是使用快速排序对数组元素进行排序的代码。

void QuickSort(int a[], int beg, int end)
{
    if(beg<end)
    {
        int p=Partition(a,beg,end);                       
        QuickSort(a,beg,p-1);                           
        QuickSort(a,p+1,end);                        
    }
}

您可以观察到：

int p=Partition(a,beg,end);                      
QuickSort(a,beg,p-1);                             
QuickSort(a,p+1,end);  

我还没有理解在这个函数中那些递归调用是如何工作的，分区数组是如何提供给QuickSort(a,beg,p-1);和QuickSort(a,p+1,end);的。我最终介于两者之间，当我试运行或调试它时，我会感到困惑，因为它看起来像合并排序。我也知道快速排序的视觉表示（在YouTube上看到）。

谁能通过进行 x[5] 所有迭代向我解释？

#include<iostream>
#include<time.h>
using namespace std;
int z = 0;
int Partition(int a[], int beg, int end) //Function to Find Pivot Point
{
  int p = beg, pivot = a[beg], loc;
  for (loc = beg + 1; loc <= end; loc++) {
    if (pivot > a[loc]) {
      a[p] = a[loc];
      a[loc] = a[p + 1];
      a[p + 1] = pivot;
      p = p + 1;
    }
  }
  return p;
}
void QuickSort(int a[], int beg, int end) {
  if (beg < end) {
    int p = Partition(a, beg, end); //Calling Procedure to Find Pivot
    QuickSort(a, beg, p - 1); //Calls Itself (Recursion)
    QuickSort(a, p + 1, end); //Calls Itself (Recursion)
  }
}
int function_Random(int x[1000], int i) {
  if (i == 1001)
    return 0;
  x[z] = rand() % 100;
  cout << x[z] << "t";
  z++;
  function_Random(x, i += 1);
  //return x;
}
int main() {
  int s;
  static int i;
  int x[1000];
  begin = clock();
  function_Random(x, i);
  QuickSort(x, 0, 1000);
  cout << "nnAfter";
  for (i = 0; i < 1000; i++) {
    cout << "t" << x[i];
  }
  return 0;
}

Answer 1

我不确定确切的问题是什么，但如果您以非常高的级别视图考虑 QuickSort，这可能会有所帮助。

快速排序的工作原理是选择一个元素作为透视表，然后将序列中的元素重新排序为两个子序列，这两个子序列的值较小和较大，由透视分隔。此时，枢轴已就位，您只需独立对两个序列进行排序。

繁重的工作是通过分区完成的，该分区遍历序列，将原始序列分成两个子序列并产生枢轴的最终位置。 请注意，分区完成后，透视表位于其最终位置，无需移动。

在您的情况下，枢轴被选为第一个元素，因此您将拥有：

initial:     [ pivot, other elements... ]
partitioned: [ smaller..., pivot, larger... ]

此时，您可以快速排序子序列[ smaller... ]和[ larger... ]。

请注意，这不像 mergesort，在 mergesort 中，您有一个固定的拆分点，您可以独立地对两个子序列进行排序，然后通过合并结果来构建整体解决方案。在快速排序中，选择一个元素将其移动到正确的位置，将宇宙分成构成两个子序列的较小/较大的值，拆分点由枢轴的值和所有其他元素的相对值确定。