QuickSort划分

Question

我试图从这个网站中了解快速排序算法，paul的实现速度与stl：：sort一样快(在大范围内快速排序，在较小范围内进行插入排序)。

我把保罗的实现和我的比较，我的比他的执行慢3倍。通过分析我们的代码，我发现主要的不足是分区。

以下是paul代码的摘录：

void Partition(int data[], int low , int high){
 int pivot = data[low];
 int fromLow = low;
 int fromHigh = high;
 int ptr = low;

 goto QStart;
 while(true){
    do {
        fromHigh--;
        if(fromLow >= fromHigh)
          goto QEnd;
QStart:;        
    }while(data[fromHigh] > pivot)

    data[ptr] = data[fromHigh];
    ptr = fromHigh;

    do{
        fromLow++;
        if(fromLow >= fromHigh){
          ptr = fromHigh;
          goto QEnd;
        }
    }while(data[fromLow] < pivot)
    data[ptr] = data[fromLow];
    ptr = fromLow;
 }
QEnd:;
   data[ptr] = pivot;
}

以下是我的：

void MyPartition(int data[], int low , int high){

 int pivot = data[low]; 
 int fromLow = low;
 int fromHigh = high;
 int ptr = low;
 while(fromLow != fromHigh){
    if(data[fromHigh] >= pivot)
        fromHigh--;
    else{
        data[ptr] = data[fromHigh];
        ptr = fromHigh;

        while(data[fromLow] <= pivot && fromLow != fromHigh)
            fromLow ++;
        data[ptr] = data[fromLow];
        ptr = fromLow;
    }
 }
 data[ptr] = pivot;
}

这两个函数实现相同的算法，我相信它们具有相同的BigO：

1. 首先，从高端到低端(右=>左)的扫描数组用于查找第一个值的值小于pivot。
2. 然后，从低端到高端的扫描数组(左=>右)查找第一个值的值大于pivot。
3. 在任何一种扫描中，如果发现了什么，那么我们就“用枢轴值交换它”，这是逻辑交换，因为pivot值是用变量 pivot 缓存的，所以我们可以将变量ptr看作当前的枢轴值位置。

有人知道为什么保罗的实现速度比我快吗？

更新

int PartitionData2(int * data, int low, int high){
  int pivot = data[low]; 
  int fromLow = low;
  int fromHigh = high;
  int ptr = low;

  while(fromLow < fromHigh){      
    if(data[fromHigh] > pivot)           // '>=' ==> '>'
      fromHigh--;   
    else{
      data[ptr] =data[fromHigh] ;
      ptr = fromHigh;      

      while(data[++fromLow] < pivot &&   // '<=' ==> '<'
            fromLow != fromHigh);

      data[ptr] = data[fromLow];
      ptr = fromLow;
      fromHigh--;                        // antti.huima's idea
    }
  }
  data[ptr] = pivot;
  return ptr;
}

我只是根据antti.huima的思想更新代码，这使得我的代码和保罗的代码一样快。

这让我感到困惑，因为它看起来像交换值，相当于支点。

UPDATE2：我理解为什么我们需要相当于支点的move元素，因为如果我们不这样做，两个新分区将是不均匀的，例如，应该有一个比另一个大得多。它最终进入O(n^2)的情况。

请参阅此PDF

Answer 1

您的代码中有一些paul代码没有的冗余检查。

例如，在线路上

   while(data[fromLow] <= pivot && fromLow != fromHigh)

第一次检查在第一次迭代中是多余的，因为它始终认为，当您开始此迭代时，第一次迭代的datafromLow不高于支点。原因是，每当您开始此迭代时，您只需交换一个小于“from this”中的支点的值。因为对于随机有序数组，这个迭代只运行几个循环(随机支点以50%的概率结束)，与paul的代码相比，实际上要进行25%的额外比较，后者在极限检查之前不进行枢轴比较，而是先增加一次fromLow。

在减少fromHigh的第一个循环中，您有相同的性能错误，尽管它在语法上是不同的。保罗的密码没有..。这就是为什么他需要去QStart :)