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

Question

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

---

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

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

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);
    }

    /////////

注意:我对此进行了修改，使子问题变得更小(o.w. 例如，您可以将 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;
    }

让我知道这是否有效