结合QuickSort和中位数选择算法 [英] Combine QuickSort and Median selection algorithm

问题描述

我想修改QuickSort(在Java中)，以便每次调用Partition时，都将比例数组的中位数用作枢轴.

I want to modify QuickSort (in Java) so that every time Partition is called, the median of the proportioned array is used as the pivot.

我有一个Java中位数选择算法，该算法返回第k个最小元素，在这种情况下为中位数.我在Java中有大量的快速排序算法，它们全靠自己工作并对数组进行排序.不幸的是，我无法将两者结合起来以实现上述目标.每次尝试时，我通常都会遇到stackoverflow错误.

I have a median selection algorithm in Java that returns the kth smallest element, in this case the median. I have tons of quicksort algorithms in java that all work by themselves and sort an array. Unfortunately I can't combine those two in order to achieve the above... Everytime I try it i usually get stackoverflow erros.

任何人都可以给我看代码以查看如何完成吗?

Can anybody show me code to see how it can be done?

谢谢

例如，这是我尝试使用的中位数选择算法.

For example this is a median selection algorithm that I have tried to use.

public int quickSelect(int[] A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Partition(A,p,r);
    int len = q-p+1;

    if (k == len) return A[q];
    else if (k<len) return Select(A,p,q-1,k);
    else return Select(A,q+1,r,k-len);
}

public int partition(int[]A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j = p; j<=r-1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

它本身可以工作，但是当我尝试通过quicksort的分区函数调用quickSelect来返回要使用的数据透视表时，它不起作用.显然我在做错事，但我不知道该怎么办.不幸的是，在Internet上，我什至没有发现任何算法，即使是伪代码，也无法将中位数选择与快速排序结合在一起.

It works by itself but when I try to call quickSelect through quicksort's partition function to return the pivot to be used, it doesn't work. Obviously I'm doing something wrong but I don't know what. Unfortunately on the Internet I haven't found any algorithm, even in pseudocode, that would combine a median selection with quicksort.

推荐答案

您可以使用此...

int Select(int array[],int start, int end,int k){

if(start==end){
    return start;
}

int x=array[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
    if(array[j]<x){
        i++;
        Swap(array+i,array+j);
    }
}
i++;
Swap(array+i,array+end);

if(i==k){
    return i;
}
else if(i>k){
    return Select(array,start,i-1,k);
}
else{
    return Select(array,i+1,end,k);
}

}

Select将对数组中的第k个最小元素进行分区；

Select will partition array on kth smallest element in array;

这篇关于结合QuickSort和中位数选择算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！