经典算法 BFPRT算法详解

问题描述：给定一个整型数组，返回其中第K小的数

普通解法：
  这道题可以利用荷兰国旗改进的 partition 和随机快排的思想：随机选出一个数，将数组以该数作比较划分为 <,=,> 三个部分，则 = 部分的数是数组中第几小的数不难得知，接着对 < （如果第K小的数在 < 部分）或 > （如果第K小的数在 > 部分）部分的数递归该过程，直到 = 部分的数正好是整个数组中第K小的数。这种做法不难求得时间复杂度的数学期望为 O(NlogN) （以2为底）。
但这毕竟是数学期望，在实际工程中的表现可能会有偏差(最坏情况下的时间复杂度会达到O(N^2))
  BFPRT算法可以说是这种算法的一种优化吧

	public static int process(int[] arr, int L, int R, int index) {
		if(L == R) {
			return arr[L];
		}
		//等概率随机选取一个值作划分    L+ [0,R-L]
		int pivot = arr[L+(int)(Math.random()*(R-L+1))];
		
		//range[0]   range[1]
		//    L   ....  R         pivot
		int[] range = partition(arr,L,R,pivot);
		
		if(index >= range[0] && index <= range[1]) {
			return arr[index];
		} else if(index < range[0]) {
			return process(arr,L,range[0]-1,index);
		} else {
			return process(arr,range[1]+1,R,index);
		}
		
		
	}
	
	public static int[] partition(int[] arr,int L, int R, int pivot) {
		int less = L - 1;
		int more = R + 1;
		int cur = L;
		while(cur < more) {
			if(arr[cur] < pivot) {
				swap(arr,++less,cur++);
			} else if(arr[cur] > pivot) {
				swap(arr,cur,--more);
			} else {
				cur++;
			}
		}
		return new int[] {less + 1, more - 1};
	}
	
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

BFPRT算法
  BFPRT算法，又称为中位数的中位数算法，有5位大牛（Blum、Floyd、Pratt、Rivest、Tarjan）提出，并以他们的名字命名。

BFPRT算法能够做到时间复杂度就是 O(N)
BFPRT算法，接收一个数组和一个K值，返回数组中的一个数

1. 数组被划分为了 N/5 个小部分，每个部分的5个数排序需要 O(1) ，所有部分排完需要 O(N/5)=O(N)

2. 取出每个小部分的中位数，一共有 N/5 个，递归调用BFPRT算法得到这些数中第 (N/5)/2 小的数（即这些数 的中位数），记为 pivot

3. 以 pivot 作为比较，将整个数组划分为 <pivot , =pivot , >pivot 三个区域

4. 判断第K小的数在哪个区域，如果在 = 区域则直接返回 pivot ，如果在 < 或 > 区域，则将这个区域的数递 归调用BFPRT算法

5. base case ：在某次递归调用BFPRT算法时发现这个区域只有一个数，那么这个数就是我们要找的数

	// arr[L..R] 如果排序的话，位于index位置的数，是什么，返回什么
	public static int bfprt(int[] arr, int L, int R, int index) {
		if(L == R) return arr[L];
		int pivot = medianOfMedians(arr,L,R);
		int[] range = partition(arr,L,R,pivot);
		if(index >= range[0] && index <= range[1]) {
			return arr[index];
		} else if(index < range[0]) {
			return bfprt(arr,L,range[0]-1,index);
		} else {
			return bfprt(arr,range[1]+1,R,index);
		}
	}
	
	//arr[L..R] 五个数一组
	//每个小组内部排序
	//每个小组中位数拎出来，组成mArr
	//mArr中的中位数，返回
	public static int medianOfMedians(int[] arr, int L, int R) {
		int size = R - L + 1;
		int offset = size % 5 == 0 ? 0 : 1;
		int[] mArr = new int[size / 5 + offset];
		for(int team = 0; team < mArr.length; team++) {
			int teamFirst = L + team *5;
			mArr[team] = getMedian(arr,teamFirst,Math.min(R, teamFirst));
		}
		return bfprt(mArr,0,mArr.length-1,mArr.length / 2);
	}
	
	//五个数排序，返回中位数
	public static int getMedian(int[] arr,int L, int R) {
		insertionSort(arr,L,R);
		return arr[(L+R) / 2];
	}
	
	public static void insertionSort(int[] arr,int L,int R) {
		for(int i = L +1; i <= R; i++) {
			for(int j = i - 1; j >= L && arr[j] > arr[j+1]; j--){
				swap(arr,j,j+1);
			}
		}
	}

时间复杂度分析：
  BFPRT算法在最坏情况下的时间复杂度是O(n)，下面予以证明。令T(n)为所求的时间复杂度，则有:

其中:

• T(n/5)来自medianOfMedians()， n个元素，5个一组，共有 n/5 个中位数;
• T(7n/10)来自bfprt()，在 n/5 个中位数中，主元pivot 大于(1/2)*(n/5)=n/10 的中位数，而每个中位数在其本来的5个数的小组中又大于或等于其中的3个数，所以主元pivot 至少大于所有数中的 (n/10)*3=3n/10 个。即划分之后，任意一边的长度至少为 3/10，在最坏情况下，每次选择都选到了 7/10 的那一部分。
• C·n来自其它操作，比如insertionSort()，以及getMedian()和partition()里所需的一些额外操作。

  设T(n)=t·n，其中t为未知，它可以是一个正常数，也可以是一个关于n的函数，代入上式︰

  其中c为一个正常数，故t也是一个正常数，即T(n)≤10c ·n，因此T(n)=O(n)，至此证明结束。