选择问题解决算法--快速选择（quickselect）

1.基本思想

选择问题：有一组N个数而要确定其中第k个最小（或最大）者

快速选择算法几乎与快速排序相同
算法步骤
以确定第k个最小者为例

1. 如果N = 1，那么k = 1将数组中的元素返回
2. 如果N小于等于CUTOFF（小数组的截止方法），那么将数组直接插入排序并返回第k个最小元素
3. 如果不是上面的两种情况，那么选取枢轴
4. 将数组分为左右两子数组（和快速排序一样）
5. 如果k小于等于左子数组的长度，那么所求元素必在左子数组，对左子数组继续进行递归快速选择。
   如果k等于左子树长度加一，那么枢轴就是所求元素。
   如果k大于左子数组的长度，那么所求元素必在右子数组，对右子数组进行递归快速选择，此时k变为(k-左子数组长度-1）

2.算法实现

	public static <AnyType extends Comparable<? super AnyType>> AnyType quickselect(AnyType[] a,int k)
	{
		quickselect(a, 0, a.length - 1, k);
		
		return a[k - 1];
	}
	
	private static final int CUTOFF = 3;//截止范围

	
	private static <AnyType extends Comparable<? super AnyType>> void quickselect(AnyType[] a, int left, int right, int k)
	{
		if(left + CUTOFF <=  right)
		{
			AnyType pivot = median3(a, left, right);//储存枢轴
			
			int i = left;//左指针
			int j = right - 1;//右指针
			
			
			while(true)
			{
				while(a[++i].compareTo(pivot) < 0) {};//左指针移动，当移动到一个较大元素时停止，注意先加一再调用
				while(a[--j].compareTo(pivot) > 0) {};//右指针移动，当移动到一个较小元素时停止，注意先减一再调用
				
				if(i < j)
					swapReferences(a, i, j);
				else
					break;
			}
			
			swapReferences(a, i, right - 1);//左右指针重合时，将枢轴放入数组中，左边为小数组，右边为大数组
			if(k <= i)
				quickselect(a, left, i - 1, k);//对小数组进行快速选择
			else if(k > i + 1)
				quickselect(a, i + 1, right, k);//对大数组进行快速排序
			
		}
		else
			insertion(a, left, right);
		
	}
	
	//三数中值分割法
	private static <AnyType extends Comparable<? super AnyType>> AnyType median3(AnyType[] a, int left, int right)
	{
		int center = (left + right) / 2;//确定中值角标
		
		//将left,center,right角标上的元素按从大到小顺序排列
		if(a[center].compareTo(a[left]) < 0)
			swapReferences(a, left, center);
		if(a[right].compareTo(a[left]) < 0)
			swapReferences(a, right, left);
		if(a[right].compareTo(a[center]) < 0)
			swapReferences(a, right, center);
		
		//将center与right - 1交换位置
		swapReferences(a, center, right - 1);
		
		return a[right - 1];
		
		
	}
	
	//交换两个元素位置
	public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2)//不需要继承Comparable，没用到比较方法
	{
		AnyType tmp = a[index1];
		a[index1] = a[index2];
		a[index2] = tmp;
	}
	
	//面对小数组的插入排序
	private static <AnyType extends Comparable<? super AnyType>> void insertion(AnyType[] a, int left, int right)
	{
		
		for(int p = left + 1; p <= right; p++)
		{
			AnyType tmp = a[p];
			int j;
			for(j = p ; j > left && tmp.compareTo(a[j - 1]) < 0;j--)
				a[j] = a[j - 1];
			a[j] = tmp;
		}
		
	}

3.算法分析

• 与快速排序相比，快速选择只做一次递归调用而不是两次
• 快速选择是一种对于大数据非常高效的选择问题的解法