第K個最小元素算法

Question

我正在寫一個算法，該算法劃分並征服一個未分類的整數數組以找到第k個最小元素。在測試我的程序時，我的一些輸出結果出錯了。下面是代碼：

public class kthsmallest { 

public static final int MaxSize = 500; 

public static int find_kth_smallest(int[] A, int n, int k) 
{ 
     return quicksort(A, n, k, 0, n-1); 
} 

public static int quicksort(int[] A, int n, int k, int low, int high){ 
int i = low; 
int j = high; 
int position = low + (high-low)/2; 
int pivot = A[position]; 

while (i <= j){ 
    while(A[i] < pivot) 
     i++; 

    while(A[j] > pivot) 
     j--; 

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

// 
if (position + 1 > k){ 
    return quicksort(A, n, k, low, position-1); 
} else if (position + 1 < k){ 
    return quicksort(A, n, k, position+1, high); 
} else 
    return A[position]; 

如果任何人都可以看到什麼毛病此算法，請讓我知道。我一直在調試幾個小時。謝謝。

Answer 1

您將錯誤輸入1,2,3,20,4,5,6並搜索第6個元素。那是因爲在這種情況下，你將不得不交換一個元素不止一次，在我看來，你永遠不會這樣做。你會交換20和6，但之後你會增加我，因此永遠不會再交換6，而你實際上應該。 6是正確的答案。我不確定你會發現什麼價值，但它不會是6.

也可能會發生幾個問題，因爲元素等於樞軸。嘗試爲這些元素添加特殊檢查。