快速排序中的计数比较 : Wrong answer

Question

我编写了代码来计算 QuickSort 中完成的比较次数。

每当对长度为 m 的数组执行快速排序时，该算法都会将比较次数增加 m-1(因为主元将与除自身以外的所有内容进行比较)。

枢轴的选择始终是数组的第一个元素。

当我尝试在包含 10000 个条目的数组上使用它时，它给出了错误的答案。

正确答案应该是162085。

数据集的链接如下: https://drive.google.com/file/d/0B0D_kFnzj_RrYm9NT0lrM3JfN2c/view?usp=sharing

总比较结果存储在 x 中。

 #include<stdio.h>
  long long x=0;
  int size=10000;
  int A[10000];
  int B[10000];

  void quicksort(int A[],int begin,int end)
  {
  if(begin<end){
  int i=begin;
  int j=end;
  int k;
  int pivot=begin;

  for(k=begin+1;k<=end;k++)
  {
  if(A[k]>A[pivot])
  {
  x++;
  B[j]=A[k];
  j--;
  }
  else
  {
  x++;
  B[i]=A[k];
  i++;
  }
  }

  B[i]=A[pivot];

  for(k=begin;k<=end;k++)
  {
  A[k]=B[k];
  }

  quicksort(A,begin,i-1);
  quicksort(A,i+1,end);
  }
  else
  {
  if((end-begin)==1) x++;
  }
  }

  int main()
  {

  FILE *myFile;
  myFile = fopen("QuickSort.txt", "r");


  int i;
  for (i = 0; i < 10000; i++)
  {
  fscanf(myFile, "%d", &A[i]);
  }

  quicksort(A,0,size-1);

  for(i=0;i<size;i++)
  {
  printf("%d\n",A[i]);
  }

  printf("%lld",x);
  }

Answer 1

这部分是错误的:

for(k=begin+1;k<=end;k++)
{
    if(A[k]>A[pivot])
    {
        x++;
        B[j]=A[k];
        j--;
    }
    else
    {
        x++;
        B[i]=A[k];
        i++;
    }
}

你不必从头到尾。你只需从 begin 开始直到 i>j。

查看链接:https://en.wikipedia.org/wiki/Quicksort

有趣的几行是:

do
    i := i + 1
while A[i] < pivot
do
    j := j – 1
while A[j] > pivot
if i >= j then
    return j
swap A[i] with A[j]

c/c++

i = begin;
j = end;
while(true)
{
    while(i< end && A[i] < A[pivot])
    {
        i++;
    }
    while(j> begin && A[j] >= A[pivot])
    {
        j--;
    }
    if(i<j)
    {
        int temp = A[i]; //std::swap(A[i],A[j]);
        A[i] = A[j];
        A[j] = temp;
    else
    {
       break;
    }
}

在此代码中，我不使用 B，因为快速排序是一种“就地”算法，因此我们不需要将结果保存到不同的数组中