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 :)