我正在尝试通过对数组进行分区来实现快速选择，但它不断产生错误的答案。我哪里犯了错误？

Question

这是java代码

select函数返回数组中存在的第k个最小元素。尽管代码在我看来还可以，但它并没有产生正确的结果。

public static Comparable select(Comparable[] a, int k, int lo, int hi) {
if(hi <= lo) return a[--k];
int j = partition(a, lo, hi);
if(j == k-1) return a[j];
else if(j > k-1) return select(a, k, lo, j-1);
else if(j < k-1) return select(a, k, j+1, hi);
return a[--k];
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi;
Comparable pivot = a[lo + (hi - lo)/2]; // the pivot element;
while(i < j) {
while(less(a[++i], pivot)) if(i == hi) break;
while(less(pivot, a[--j])) if(j == lo) break;
exchange(a, i, j); // exchanges elements at indices i and j
}
exchange(a, lo, j); // exchanges elements at indices lo and j
return j; 
}

Answer 1

代码使用Hoare分区方案，这意味着pivot和等于pivot的元素可以在任何地方结束。这意味着在达到基本情况之前，第k个最小的元素是未知的，并且这一行应该被删除：

if(j == k-1) return a[j];