QuickSort分区

Question

我想了解从这个web site快速排序算法，paul的实现速度与stl :: sort（在大范围内快速排序，在较小范围内插入排序）一样快。

我比较了保罗和我的实施，我的实施比他的实施慢3倍。通过分析我们的代码，我发现主要的缺陷是分区。

以下是节选的形式保罗代码：

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; 
} 

这两个功能实现相同的算法，我相信他们有同样的比戈：

1. 首先，扫描阵列从高端到低端（右=>左）寻找 寻找第一个值小于pivot。
2. 然后，扫描阵列从低端到高端（左=>右） 找到第一个值大于主轴。
3. 在这两种扫描，如果有什么发现，那么我们“掉它 与支点价值”，这是合乎逻辑的交换，因为枢纽值是 可变支点缓存，我们可以把变量PTR为 当前枢纽值的位置。

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

UPDATE：

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： 我明白了为什么我们需要移动相等于转动部件的原因，因为如果我们不这样做，这两个新的分区将是不平坦的，例如应该有一个比另一个大得多。它最终会转到O（n^2）的情况。

看到this PDF

Answer 1

你在你的代码中的一些多余的检查，保罗的代码没有。

例如就行

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

第一检查是在第一次循环冗余，因为它总是认为，当你开始此迭代中，在第一次迭代的数据[fromLow]不大于枢轴更高。原因是，无论何时你开始这个迭代，你只需要交换一个小于'fromHigh'的数据。因为对于一个随机排序的数组，这个迭代只能运行几个循环（对于一个随机数据枢轴它以50％的概率终止），所以在实践中做了25％的额外比较，而保罗的代码没有进行数据透视比较在限制检查之前，先从低处增加一次。

在第一个循环中，即使它在语法上有所不同，您仍然从“高”降低，但具有相同的性能缺陷。保尔的代码没有它......这就是为什么他需要转到QStart :)