如何在QuickSort中選擇樞軸值？

Question

我一直在研究快速排序幾個小時，並且對選擇一個樞軸值感到困惑。數據透視值是否需要存在於數組中？

例如，如果數組是1,2,5,6，我們可以使用值3還是4作爲支點？

我們使用pivot的位置來將數組分割成子數組，但我們對將數組左側的值和右側的值> 5的數值移動後的樞軸位置有些困惑？

7,1,5,3,3,5,8,9,2,1 

我拼命地跑乾的算法中與樞軸5和具有以下結果出來：

1,1,5,3,3,5,8,9,2,7 
1,1,5,3,3,5,8,9,2,7 
1,1,5,3,3,5,8,2,9,7 

我們可以看到，值2仍然沒有在正確的位置。我究竟做錯了什麼？對不起，如果這是一個愚蠢的問題。

我想出了以下代碼，但它只在pivot = left時才起作用，我不能使用隨機數據透視表。

template <class T> 
void quickSort(vector <T> & arr, int p, int r, bool piv_flag) { 
    if (p < r) { 
     int q, piv(p); counter++; 

     //piv = ((p + r)/2); doesn't work 

     q = partition(arr, p, r, piv); 
     quickSort(arr, p, q - 1, piv_flag); //Sort left half 
     quickSort(arr, q + 1, r, piv_flag); //Sort right half 
    } 

    return; 
} 

int partition(vector <T> & arr, int left, int right, int piv) { 
    int i{ left - 0 }, j{ right + 0 }, pivot{ arr[piv] }; 

    while (i < j) { 
     while (arr[i] <= pivot) { i++; } 
     while (arr[j] > pivot) { j--; } 
     if (i < j) (swap(arr[i], arr[j])); 
     else { 
      swap(arr[j], arr[piv]); 
      return j; 
     } 
    } 
} 

謝謝。

Answer 1

在許多應用程序中，數據透視表是作爲數組中的某個元素選擇的，但它也可以是任何值，可用於將數組中的數字分隔爲兩個。如果您選擇的數值是數組中的特定元素，則在將數組分成兩部分後，需要將它放在這兩個組之間。如果沒有，您可以通過正確調用索引來繼續遞歸排序過程。 （即記住陣列中不存在樞軸元素，而只是兩組值）

請參閱this response以獲得一個類似的問題，以便簡要說明一些廣泛使用的選擇方案以選擇數據透視。

樞軸的最重要的功能是用作我們在快速排序的分區階段創建的組之間的邊界。這裏的目標/挑戰是以這樣的方式創建這些組，使它們的大小相等或幾乎相等，以便快速排序可以有效地工作。這個挑戰是構思如此多的樞軸選擇方法的原因。 （即至少在大多數的情況下，數字將被分成相似大小的組）

至於你的問題的第二部分關於一旦分區完成後，數據透視的位置將如何改變，請參閱下面是一個樣本分區階段。

假設我們有一個元素爲[4,1,5,3,3,5,8,9,2,1]的數組A，我們選擇pivot作爲第一個元素，即4.使用字母E下面表示比樞軸更小的元素的末端。 （即，除所述樞轉較小的最後一個元素）

E 
[4,1,5,3,3,5,8,9,2,1] 

    E 
[4,1,3,5,3,5,8,9,2,1] 

     E 
[4,1,3,3,5,5,8,9,2,1] 

     E 
[4,1,3,3,2,5,8,9,5,1] 

      E 
[4,1,3,3,2,1,8,9,5,5] 

[1,1,3,3,2,4,8,9,5,5] // swap pivot with the rightmost element that is smaller than its value 

這種劃分之後，將元件仍然沒有排序，很明顯。但是4的左邊的所有元素都小於4，右邊的所有元素都大於4.爲了對它們進行排序，我們遞歸地在這些組上使用Quicksort。

根據您的代碼，以下是基於上述過程的示例分區代碼。您也可以觀察其執行here。

template <class T> 
int partition(vector<T>& arr, int left, int right, int piv) { 
    int leftmostSmallerThanPivot = left; 

    if(piv != left) 
     swap(arr[piv], arr[left]); 
    for(int i=left+1; i <= right; ++i) { 
     if(arr[i] < arr[left]) 
      swap(arr[++leftmostSmallerThanPivot], arr[i]); 
    } 
    swap(arr[left], arr[leftmostSmallerThanPivot]); 
    return leftmostSmallerThanPivot; 
} 

template <class T> 
void quickSort(vector<T>& arr, int p, int r) { 
    if (p < r) { 
     int q, piv(p); 

     piv = ((p + r)/2); // works 

     q = partition(arr, p, r, piv); 
     quickSort(arr, p, q - 1); //Sort left half 
     quickSort(arr, q + 1, r); //Sort right half 
    } 
}