package demo67;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List;import java.util.TreeMap;/** * 取数组中的第几大数 * @author mengfeiyang * */public class GetNBig {	public static void main(String[] args) {		test25();		TreeMap
    
      hm = new TreeMap
     
      ();		List
      
        list = new ArrayList
       
        ();		int a[] = {1,8,6,9,0,5,7,6};		int n = 4;//取第几大的数		for(int b : a){hm.put(b, b);list.add(b);}		System.out.println("map:"+hm.values());				list.sort(new Comparator
        
         () {			@Override			public int compare(Integer o1, Integer o2) {				return -(o1-o2);//从大到小排序			}		});				System.out.println("list:"+Arrays.toString(list.toArray()));		System.out.println(choose_nth(a,0,a.length-1,n));				fast_sort(a,0,a.length-1);		System.out.println(Arrays.toString(a));	}		//快速排序方法	public static void fast_sort(int a[], int startIndex, int endIndex)	{	    int midOne = a[startIndex];//选第一个作为参考点	    int i = startIndex, j = endIndex;	    if(i < j)//这个判断是递归结束的依据,不加的话会导致堆栈溢出	    {	        while(i < j)	        {	            for(; i < j; j--){		            if(a[j] < midOne)//小于参考点的数移到左边		            {		                a[i++] = a[j];		                break;		            }	            }	            for(; i < j; i++){		            if(a[i] > midOne)//大于参考点的数移到右边		            {		                a[j--] = a[i];		                break;		            }	            }	        }	    	        a[i] = midOne;//参考点归位	        //把参考点左右的部分分别进行快排	        fast_sort(a, startIndex, i - 1);	        fast_sort(a, i + 1, endIndex);	    }	}		//使用快速排序获取到第n大值	public static int choose_nth(int a[], int startIndex, int endIndex, int n)	{	    int midOne = a[startIndex];	    int i = startIndex, j = endIndex;	    if(i == j) //递归出口之一	        return a[i];	    if(i < j)	    {	        while(i < j)	        {	            for(; i < j; j--){		            if(a[j] < midOne)		            {		                a[i++] = a[j];		                break;		            }	            }	            for(; i < j; i++){		            if(a[i] > midOne)		            {		                a[j--] = a[i];		                break;		            }	            }	        }	        a[i] = midOne;//支点归位	        int th = endIndex - i + 1;//计算下标为i的数第几大	        if(th == n)//正好找到	        {	            return a[i];	        }	        else	        {	            if(th > n )//在支点右边找	                return choose_nth(a, i + 1, endIndex, n);	            else//在支点左边找第(n-th)大,因为右边th个数都比支点大	                return choose_nth(a, startIndex, i - 1, n - th);	        }	    }		return -1;	}		public static void test21(){		int tmp = 0;		for(int i=0;i<8;i++){			for(int j=0;j<=i;j++){				System.out.print((tmp++)+"\t" );			}			System.out.println();		}	}		static int s = 8;	static int c = 0;	static int tmp = 0;	public static void test22(){		for(int j=0;j<=c;j++)System.out.print((tmp++)+"\t" );		System.out.println();		c++;		if(c