1

我正在编写一个算法，该算法通过划分和征服一个未排序的整数数组来找到第 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];

如果有人能看出这个算法有什么问题，请告诉我。我已经调试了几个小时。谢谢。

4

1 回答 1

1

1,2,3,20,4,5,6输入和搜索第 6 个元素会出错。那是因为在这种情况下，您将不得不多次交换一个元素，而在我看来，您从不这样做。您将交换 20 和 6，但之后您将增加 i，因此将永远不会再交换 6，而您实际上应该这样做。6 是正确答案。我不确定你会找到什么值，但它不会是 6。

由于元素等于枢轴，也可能会发生一些问题。尝试为此类元素添加特殊检查。

于 2013-03-08T21:56:27.680 回答