【解析】

受快速排序的启发，在快速排序中，现在数组中选择一个数字，然后调整数组中的数字的顺序，使得比选中数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边。

如果选中的数字的下标刚好是n/2，那么这个数字就是数组中的中位数。

import java.util.Scanner;
 
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		
		int[] num=new int[n];
		
		for(int i=0;i<n;i++){
			num[i]=in.nextInt();
		}
	   int b=GetHalfNum(n,num);
	   if(b!=-1){
		  System.out.println(b);	
	   }
 
	}
	public static int GetHalfNum(int uiInputNum, int[] pInputArray){
		  if(pInputArray==null||uiInputNum<=0){
			 return -1; 
		  }
		  int middle=uiInputNum>>1;//长度的一半
		  int start=0;
		  int end=uiInputNum-1;
		  int index=partition(pInputArray,start,end);
		  while(index!=middle){//如果不等于长度的一半说明就没有找到这个中位数
			    if(index>middle){
			    	 end=index-1;
			    	 index=partition(pInputArray,start,end);
			    }
			    else{
			    	start=index+1;
			    	index=partition(pInputArray,start,end);
			    }
		  }
		  
		  return pInputArray[index];//index=middle
		  
	}
	
	public static int partition(int[] a,int start,int end){
		  int privot=a[start];
		  int i=start;
		  int j=end;
		  while(i<j){
			  while(i<j&&privot<=a[j]){
				  j--;
			  }
			  swap(a,i,j);
			  while(i<j&&privot>=a[i]){
				  i++;
			  }
			  swap(a,i,j);
		  }
		  return i;
		  
	}
	public static void swap(int[] a,int i,int j){
		int t=a[i];
		a[i]=a[j];
		a[j]=t;
	}
}