在没有排序的情况下查找java中的中位数
我需要在java中编写一个程序来查找三个或更多整数数组的中位数而不进行排序。 我需要一些想法。 谢谢
您可以使用选择算法 。 您还可以找到寻找中位数中位数的相关信息。
您可以使用随机支点快速排序分区步骤，而无需对其进行排序。
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; } }