選擇算法有時會返回錯誤的結果

對於作業問題，我需要編寫一個Java方法來使用quicksort風格的分區來查找數組中第k個最小的數字。我得到了partition（）方法，並且我應該編寫該方法來獲得第k個最小的數字。選擇算法有時會返回錯誤的結果

問題要求數據透視表始終是數組範圍中最右邊的元素。

我得到以下幾點：

public int partition(int left, int right, long pivot) { 
    int leftPtr = left - 1; 
    int rightPtr = right + 1; 
    while (true) { 
     while (leftPtr < right && array[++leftPtr] < pivot); 
     while (rightPtr > left && array[--rightPtr] > pivot); 

     if (leftPtr >= rightPtr) 
      break; 
     else 
      swap(leftPtr, rightPtr); 
    } 
    return leftPtr; 
}

而且我已經寫了基於Wikipedia's pseudocode這種方法：

public int kthSmallest(int left, int right, int k){ 
    if(left >= right){ 
     return array[left]; 
    } 

    int pivotNewIndex = partition(left, right, array[right]); 

    int pivotDist = pivotNewIndex - left - 1; 

    if(pivotDist == k){ 
     return array[pivotNewIndex]; 
    } else if(k < pivotNewIndex){ 
     return kthSmallest(k, left, pivotNewIndex - 1); 
    } else{ 
     return kthSmallest(k - pivotDist, pivotNewIndex + 1, right); 
    } 
}

但是，當我打電話kthSmallest()與整數，約有一半的隨機生成陣列它會返回錯誤的值。例如：

array: [45, 60, 24, 82, 87, 79, 16, 32, 59, 83, 20, 2, 1, 
     50, 11, 79, 72, 32, 0, 48, 69, 74, 22, 6, 96] 
expected result when k=4: 11 
actual result when k=4: 87

我在做什麼錯？

來源

2012-05-10 Rubicon

難道我們假設你不能快速排序排序，然後就跳到指數？如果不是，輸出數組以確保它實際上按正確的順序。 – Thomas

不，排序是禁止的。 – Rubicon