修改在中位数快速排序的中位数中找到的第 k 个元素

Question

注意：这个问题是昨天深夜发布的，没有得到足够的答案。我添加了一些细节并重新发布。

---

作为一项任务，我的任务是创建中位数排序的中位数，它也可以确定数组的第 n 个最小元素(即排序数组的索引 0 是第 1 个最小的元素)。这种排序是递归的，这导致了我理解它的问题，因为我没有广泛地使用递归。

通过拼凑教程和对算法的研究，我已经非常接近成功创建该方法;但是，我目前返回了错误的值。QS(A， 1) 的输入将返回索引 1 处包含的值，当我希望它返回索引 0 处的值时：

public static int QS(int[] A, int k){
List<Integer> AList = new ArrayList<Integer>();
if(k < 1 || k >= A.length){
System.out.println("Code called because k = "+k);
return -1;
}
for (int i = 0; i < A.length; i++){
AList.add(A[i]);
}
if (AList.size() < 14) {
Collections.sort(AList);
return AList.get(k);
}
ArrayList<Integer> medians = new ArrayList<Integer>();
for (int i = 0; i < AList.size() - AList.size() % 7; i = i + 7){
medians.add(medianFind(AList.subList(i, i + 7)));
}
int a = medianFind(medians);
ArrayList<Integer> left = partitionFind(AList, a, true);
ArrayList<Integer> right = partitionFind(AList, a, false);
int[] leftArray = new int[left.size()];
int[] rightArray = new int[right.size()];
for(int i = 0; i < left.size(); i++){
leftArray[i] = left.get(i);
}
for(int i = 0; i < right.size(); i++){
rightArray[i] = right.get(i);
}   
if(left.size() + 1 == k){
return a;
}
else if(left.size() > k){
return QS(leftArray, k);
}
else{
return QS(rightArray, k - left.size());
}
}
/////////
public static int medianFind(List<Integer> AList) {
Collections.sort(AList);
return AList.get(AList.size() / 2);
}
/////////
public static ArrayList<Integer> partitionFind(List<Integer> AList, int b, boolean lessThan) {
ArrayList<Integer> store = new ArrayList<Integer>();
for (int element : AList)
if (element < b && lessThan)
store.add(element);
else if (element >= b && !lessThan)
store.add(element);
return store;
}

我很难理解这个算法中的递归，以便将最终返回的索引修改为 -1。我不能简单地进行以下更改：

if (AList.size() < 14) {     //old 
Collections.sort(AList);
return AList.get(k);
}
if (AList.size() < 14) {     //new 
Collections.sort(AList);
return AList.get(k-1);
}

因为这有时会导致return QS(rightArray, k - left.size())传递小于 1 的参数。我也不认为我可以添加一个：

if(nothing left to sort){
return AList.get(k-1) 
}

由于算法的递归性质的语句。我已经在这个领域工作了很长时间，但没有成功，并且非常感谢任何关于我应该解决这个问题的迹象。

Answer 1

//returns the k^th smallest element in the array A for 0<k<A.length  
public static int QuickSelect(int[] A, int k){
List<Integer> AList = new ArrayList<Integer>();
if(A.length<k||k<1){
System.out.println("k out of range, got k: "+k +", but A.length: "+A.length);
return -1;
}
for (int i = 0; i < A.length; i++){
AList.add(A[i]);
}

此时我们知道AList.size()>0，所以得到元素 k-1，它是列表中的第 k 个最小元素

if (AList.size() < 14) {
Collections.sort(AList);
return AList.get(k-1);
}
ArrayList<Integer> medians = new ArrayList<Integer>();

for (int i = 0; i < AList.size() - AList.size() % 7; i = i + 7){
medians.add(medianFind(AList.subList(i, i + 7)));
}

你忘了找到最后AList.size()-( AList.size() % 7)元素的中位数

int a = medianFind(medians);
ArrayList<Integer> left = partitionFind(AList, a, true);
ArrayList<Integer> right = partitionFind(AList, a, false);

添加了med变量以计算中位数的出现次数

int med=AList.size()-(left.size()+right.size())
int[] leftArray = new int[left.size()];
int[] rightArray = new int[right.size()];
for(int i = 0; i < left.size(); i++){
leftArray[i] = left.get(i);
}
for(int i = 0; i < right.size(); i++){
rightArray[i] = right.get(i);
}   

不完全确定其余部分的逻辑，但我认为以下内容更有意义(请注意，我修改了 PartitionFind)

if(left.size() >= k){
return QuickSelect(leftArray, k);
}
else if(left.size()+med<k){
return QuickSelect(rightArray, k-(left.size()+med));
}
else{
return a;
}
}
/////////
public static int medianFind(List<Integer> AList) {
Collections.sort(AList);
return AList.get(AList.size() / 2);
}
/////////

注意：我修改了它，以便子问题变得严格变小(例如，您可以将 b 作为列表中最大的元素，并且右数组仍将包含整个列表)

public static ArrayList<Integer> partitionFind(List<Integer> AList, int b, boolean lessThan) {
ArrayList<Integer> store = new ArrayList<Integer>();
for (int element : AList)
if (element < b && lessThan)
store.add(element);
else if (element > b && !lessThan)
store.add(element);
return store;
}

让我知道这是否有效