c++ - 在 C++ 中围绕中位数进行分区的快速排序实现

Question

我努力自己解决这个问题，但这让我更加困惑。我查看了那些使用中位数对其进行分区的快速排序示例代码，我在一个示例数组上尝试了 A={1,8,4,6,7,10,11} 但我没有得到正确分区。分区代码如下:

void swap(int &x, int &y){
    int temp=x;
    x=y;
    y=temp;
 }
//
int partition(int arr[],int low,int high){
int pivot=arr[(low+high)/2];
while(low<=high){
   while(arr[low]<pivot) low++;
   while(arr[high]>pivot) high--;
   if(low<=high){
      swap(arr[low],arr[high]);
      low++;
      high--;
    }
 }
 return low;
}

在我的示例中，主元是 6，因此代码首先交换数组 A 中的 8 和 6，然后停止。它不会将所有小于 pivot=6 的值放在前面，将较大的值放在上面。我想问题是我们假设我们总是可以从枢轴的左侧和右侧找到两个值进行交换，但这个例子右侧很好。任何意见或想法将不胜感激。
只是一些更新:(1)我在这里的重点是快速排序的分区部分，我知道以下步骤执行递归方法。(2)我什至在这个网站的许多链接中都看到了这种方法 Quick Sort - Middle Pivot implementation strange behaviour(或在“破解编码面试”一书，第 119 页，用 Java 编写)他们声称它有效，但我对此表示怀疑(我的意思是分区部分，它可能出于任何原因以某种方式结束排序数组，但正确的分区必须实现，以便所有小于分区元素的数字都出现在所有大于它的元素之前。)在我的示例数组 A 中，它最终为 A={1,6,4,8,7,10,11这不是一个正确的分区，因为 4 在 6(我们的主元)之后。

Answer 1

您的分区实现中存在一些明显的错误。其中一个较大的问题是您不会重新比较您交换的元素。

当你在快速排序中划分时，你只需要将大于枢轴的元素移动到枢轴元素之后。所以，一个简单的实现是......

int partition(int arr[], int begin, int end) {

  int pivot = arr[begin + ((end - begin) / 2)];

  while (begin != end) {

    if (arr[begin] < pivot)
      begin++;
    else
      swap(arr[begin], arr[end--]);
  }

  return end;
}

请注意，复杂性取决于主元的质量，这就是为什么中位数是理想的原因。但是，这需要遍历所有元素 O(n)。

请记住，选择数组的中间并不总能提供良好的轴心。有一些策略可以选择一个好的基准(随机化、样本和中位数，等等......)。