快速排序分区

Question

我正在尝试从这个网站了解快速排序算法：网站链接，Paul的实现速度与stl::sort(大范围内的快速排序，小范围内的插入排序)一样快。

我将Paul的实现与我的实现进行对比，我的实现比他的慢3倍。通过对我们的代码进行分析，我发现主要差异在于Partition（划分）。

以下是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. 首先，从高端到低端（从右到左）扫描数组，以寻找第一个小于枢轴的值。
2. 然后，从低端到高端（从左到右）扫描数组，以寻找第一个大于枢轴的值。
3. 在任一扫描中，如果找到任何东西，则我们将其与枢轴值“交换”，这是逻辑上的交换，因为 枢轴值 被缓存到变量 pivot 中，我们可以将变量 ptr 视为当前的 枢轴值 位置。

有人知道为什么 Paul 的实现比我的快吗？

更新：

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的思路更新了代码，这使得我的代码和paul的代码一样快。

这让我感到困惑，因为它看起来像是交换与枢轴相等的值。

更新2： 我理解为什么我们需要移动与枢轴相等的元素，因为如果不这样做，两个新的分区将会不平衡，例如一个分区可能比另一个要大很多。最终会导致O（n ^ 2）的情况。

请参见此PDF文档

- Chang

---

@Chang，当你说他的算法更快时，是指它具有不同的渐近行为，还是仅仅是对于给定的输入需要更少的时间？ - dsolimano

“相同”的算法在大O行为上相同，但是速度可能会因机器代码的具体操作、数据结构选择等因素而有一个或多个数量级的差异。如果你在汇编代码级别单步执行，你会看到如何加速你的代码。 - Mike Dunlavey

@dsolimano，我的意思是对于给定的输入需要更少的时间。 - Chang

@MikeDunlavey，我在反汇编代码中没有看到太大的区别。 我只是怀疑这是由分支惩罚引起的。 - Chang

你是否真的手动逐条执行了一个现实的小数据集，对两个程序都这样做了？计算指令数量，并在执行过程中通过参考源代码来跟踪每个指令的原因？ - Mike Dunlavey

Answer 1

你的代码中有些冗余的检查，而Paul的代码中没有这些检查。

例如，在这一行：

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

第一次检查在第一次迭代中是冗余的，因为当你开始这个迭代时，从data[fromLow]到pivot之间没有更高的值。原因是每当你开始这个迭代时，你刚刚从'fromHigh'中交换了一个小于pivot的值。对于随机排序的数组，这个迭代只运行几次循环（对于随机枢轴，它以50%的概率终止），因此与Paul的代码相比，在实践中做了额外25%的比较，Paul的代码在限制检查之前不进行枢轴比较，但首先增加fromLow，因此性能更好。

在第一个循环中，你同样存在性能缺陷，即使语法上有所不同，而Paul的代码没有这个问题... 这就是他需要使用goto QStart的原因 :)

- Antti Huima

---

我将代码更新为 while(data[++fromLow] <= pivot && fromLow != fromHigh); 但它仍然很慢。你能否提供你的更新后的代码？ - Chang