在没有排序的情况下在java中找到中位数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22096554/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the median in java without sorting
提问by user3352641
I need to write a program in java to find the median of an array of three or more integers without sorting. I need some ideas. thanks
我需要在java中编写一个程序来在不排序的情况下找到三个或更多整数的数组的中位数。我需要一些想法。谢谢
回答by SylvainD
You can use a Selection Algorithm. You'll also find relevant information looking for Median of Medians.
您可以使用选择算法。您还可以找到寻找Median of Medians 的相关信息。
回答by mok
You can use Quick sort partitioning step with random pivots, without sorting it.
您可以使用带有随机支点的快速排序分区步骤，而不对其进行排序。
public class TestMedian {
public static void main(String[] args){
int[] a = {1,9,-4,7,6,11,3,2,10};
int median;
median = new Median().findMedian(a,0,a.length-1);
if(a.length%2 != 0)
System.out.print("the median is : "+a[median]);
else
System.out.print("the median is : "+(a[median] + a[median + 1])/2 );
}
public int findMedian(int[] a,int left,int right){
int index = 0;
int mid = (left+right)/2;
index = partition(a,left,right);
while( index != mid){
if(index < mid)
index = partition(a,mid,right);
else index = partition(a,left,mid);
}
return index;
}
public int partition(int[] a,int i,int j ){
int pivot = (i+j)/2;
int temp;
while(i <= j){
while(a[i] < a[pivot])
i++;
while(a[j] > a[pivot])
j--;
if(i <= j){
temp = a[i];
a[i]=a[j];
a[j] = temp;
i++;j--;
}
}
return pivot;
}
}
