数组中最大第K元素(快排思想)

1. 利用快排的思想找数组中最大K元素，但是找到最大K元素 是排序后的数组 地址索引为K位置上的元素

但是利用快排的思想 不需要进行排序 只需要找到 地址索引=k 位置 前k-1个元素 不一定是排序的但是 前k-1个元素一定不小于(>=)索引k位置上的值 .

快排思想：

1.进行一次快排（将大的元素放在前半段，小的元素放在后半段）, 假设得到的中轴为p=partition()

2.判断 k -1==p - low，如果成立，直接输出a[p]，（因为前半段有k - 1个大于a[p]的元素，故a[p]为第 K大的元素）

3.如果 k -1 < p - low， 则第k大的元素在前半段，此时更新high = p - 1，继续进行步骤1

4.如果 k -1 > p - low， 则第k大的元素在后半段，此时更新low = p + 1, 且 k = k -(p - low +1) ，继续步骤1.

快速排序中partition函数特性：调整函数 让大于基点元素处在前半段，小于基点元素处在后半段.

package com.offerr;

/**找 数组中 第K大的数字*/
public class Test_02 {

	public static void main(String[] args) {
		
		int [] array={10,10,10,10,20,30,30,40,40};
		
		
		//int index=Partition(array, 0, array.length-1);
		int k=4;
		System.out.print(getMaxK(array,0, array.length-1, k));
	}
	private static int count=1;//  大于index 点大的点数 index-low+1 
	private static int getMaxK(int [] array,int low ,int hign,int k)
	{
		if(low> hign)
			return -1;
		int index=Partition(array, low, hign);
		count=index-low+1;// 比基点大 的 点个数
		if(count>k)
		{
			return getMaxK(array, low, index-1, k); 
			
		}
		else if( count < k )
		{    // 点在后半部分
			return getMaxK(array, index+1,hign,k-count);
		}
		else { 
			
			return array[index];
		}
		
	}
	public static int Partition(int [] a,int low ,int high)
	{
		/**快排核心算法 先移动末指针 在移动首指针 直到 i>j
		 * 大*/
		int i=low,j=high,temp=a[low];
		if(low < high)
		{
			while(i<j)
			{
				while(i<j && temp>=a[j])
					j--;
				if(i<j)// 双重验证
				{
					a[i]=a[j];
					i++;
				}
				while(i<j && temp<=a[i])
					i++;
				if(i<j)
				{
					a[j]=a[i];
					j--;
				}
			}
			a[i]=temp;
		}
		return i;
	}
}

总结：这里无法处理 数组中重复的元素 如果数组 10 10 10 20 20 20 30 30，利用此算法得到第3大元素明显输出结果 20 。

如果我们想要第3大的元素 10 。对于这种方法

解法一：直接进行快速排序，从快速排序之后的数组中遍历数组剔除相同value的元素找到第3大的元素。

解法二：利用Set集合的特性 将数组用Set进行 处理在进行元素的排序。Java中利用集合框架TreeSet。