返回Pivot位置的分區

Question

由於正常分區返回索引j，因此索引爲i的每個元素< = j小於choisen主元，並且索引爲m> j的每個元素都大於主元，沒有保證j是關鍵。是否有可能創建另一個就地分區算法，該算法返回新的樞軸位置？ 最初，我希望將choisen樞軸放在最後的位置，但它並不會導致最佳的解決方案。

Answer 1

關鍵是保持樞軸脫離交換，除非在開始時將其存儲在一個邊界處，並在最後將其交換到正確的位置時結束。

int partition(int *A, int low, int high) { 

    if (high <= low) return low; // in that case, partition shouldn't be called, but cater for it 

    int pivot_position = low; // or high, or low + (high-low)/2, or whatever 
    int pivot = A[pivot_position]; 

    A[pivot_position] = A[high]; 
    A[high] = pivot; // these two lines are unnecessary if pivot_position == high 
    int i = low, j = high-1; 

    while(i < j) { 

     while(i < j && A[i] <= pivot) 
      ++i; // i == j or A[i] > pivot, and A[k] <=pivot for low <= k < i 

     while(i < j && A[j] > pivot) 
      --j; // i == j or A[j] <= pivot, and A[m] > pivot for j < m < high 

     if (i < j) { 
      int temp = A[j]; 
      A[j] = A[i]; 
      A[i] = temp; 
     } 
    } 
    if (A[i] <= pivot) 
     ++i; 

    // now A[k] <= pivot for low <= k < i and A[m] > pivot for i <= m < high 
    A[high] = A[i]; 
    A[i] = pivot; 
    return i; 
}