算法系列笔记2(静态表顺序统计-随机选择算法和BFPRT算法)

心已赠人 2022-08-06 14:29 133阅读 0赞

**问题**：当给定存在静态表(如数组)中的n个元素，如何快速找到其中位数、最小值、最大值、第i小的数?以及如何求出最小的k位数或者最大的k位数呢？

首先想到的方法是先对数组元素进行排序，然后找到第i小的元素。这样是可行的，但比较排序最快也需要O(nlgn)，能否在线性时间内解决呢。这就是随机的分治法—随机选择。

**1：思想**：利用随机划分(在快速排序中介绍过)找到主元r，这样就将小于等于r的元素放在了其左边，大于r的元素放在了其右边。这是可以计算出r的rank为k，如果正好等于i，则就返回该元素；如果k大于i，则在左边中寻找第i小的元素，否则在右边中寻找第i-k小的元素。

#include <iostream>
    #include <ctime>
    using namespace std;
    
    void swap(int &t1, int &t2){
    	int tmp = t1;
    	t1 = t2;
    	t2 = tmp;
    }
    
    int randomPartition(int r1[], int p, int q){
    	srand((unsigned)time(0));
    	int randInt = rand()%(q-p+1)+p;          // 随机选择一个元素作为主元
    	swap(r1[p], r1[randInt]);
    
    	int i = p, j = p+1;
    	int pivot = r1[p];
    	for(j = p+1; j <= q; j++){
    		if(r1[j] < pivot){
    			i++;
    			swap(r1[i], r1[j]);
    		}
    	}
    	swap(r1[i], r1[p]);
    	return i;
    	
    }
    
    // 随机选择算法  找到n elements, the kth smallest element
    int randomSelect(int r1[], int p, int q, int i){
    	if(p == q) return r1[p];
    	int r = randomPartition(r1, p, q);
    	int k = r - p + 1;        // 划分r1[r]左边元素个数 包括r1[r]
    	if(i == k) return r1[r];
    	if(i < k) return randomSelect(r1, p, r-1, i);     // 在左边寻找第i小元素
    	else return randomSelect(r1, r+1, q, i-k);        // 在右边寻找第i-k小元素
    }
    
    int main(){
    	int a[10] = {3,10,2,2,7,8,4,8,8,19};
    	for(int i = 1; i <= 10; i++){
    		cout << randomSelect(a, 0 ,9, i) << endl;
    	}
    	return 0;
    }

将排名前10的结果都输出来了

![Center][]

通过分析可以得出该算法的时间复杂度为O(n)，当然最坏的情况为O(n^2).

**扩展**：用以上代码求最小的k位数或者最大的k位数就比较简单了。代码如下：

// 使用随机选择算法得到无序数组中第k小的元素或者最小的k个元素，最好情况下时间复杂度为O(N),最坏为O(N^2)
    
    // 快排的划分方法
    int partition(int *arr, int l, int r){
    	srand((unsigned int)time(0));
    	int pid = rand()%(r-l+1)+l;
    	swap(arr[l], arr[pid]);
    	int pivot = arr[l];
    	int i = l, j = r;
    	while(i < j){
    		for(; j > i; j--){
    			if(arr[j] < pivot){
    				arr[i++]= arr[j];
    				break;
    			}
    		}
    
    		for(; i < j; i++){
    			if(arr[i] > pivot){
    				arr[j--] = arr[i];
    				break;
    			}
    		}
    
    	}
    	arr[i] = pivot;
    	return i;
    }
    
    
    // 用随机选择算法求取无序数组中最小的k个元素
    int randomSelect2(int *arr, int l, int r, int k, vector<int> &result){
    	int i = partition(arr, l, r);
    	int p = i - l +1;
    	if(k == p){ 
    		for(int j = l; j <= i; j++)
    			result.push_back(arr[j]);
    		return arr[i];
    	}
    	else if(k < p){
    		return randomSelect2(arr, l, i-1, k, result);
    	}
    	else{
    		for(int j = l; j <= i; j++)
    			result.push_back(arr[j]);
    		return randomSelect2(arr, i+1, r, k-p, result);
    	}
    
    }

**2：线性查找算法(BFPRT算法)**

上述随机选择算法存在的弊端是最坏情况下时间复杂度为O(N^2)，那能不能使的每次时间复杂度都为O(N)呢，这里关键在于如何选择主元，BFPRT算法就是干这事的，前面5个英文字母代表的是5个人的名字首字母。这里我们给出了如何求取第k小的元素及最小的k个元素的代码。

算法思想：

// 线性查找算法(BFPRT), 最坏情况下时间复杂度也为O(N)，克服随机选择最坏情况下的困难  
/\*  
1:将n个元素每5个一组，分成n/5(上界)组。  
2：取出每一组的中位数，任意排序方法，比如插入排序。  
3：递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。  
  
4： 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。  
  
5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。  
  
  
其时间复杂度为T(n) <= T(n/5)+T(7/10\*n)+O(n)  
\*/

代码如下：

// 插入排序
    void insertionSort(int *arr, int l, int r){
    	for(int i = l+1; i <= r; i++){
    		int temp = arr[i];
    		int j = i-1;
    		while(j >=0 && arr[j]> temp){
    			arr[j+1]= arr[j];
    			j--;
    		}
    		arr[j+1] = temp;
    	} 
    	
    }
    
    
    // 找到接近中位数的下标，不是随机选择，选择中位数的中位数的下标
    int getPivotId(int *arr, int l, int r){
    	if(r-l+1 < 5){
    		insertionSort(arr, l, r);
    		return (r+l)>>1;
    	}
    	int t = l-1;
    	for(int i = l; i+4 <=r; i= i+5){
    		insertionSort(arr, i, i+4);
    		swap(arr[++t], arr[i+2]);
    	}
    	return getPivotId(arr, l, t);
    
    }
    
    // 根据BFPRT算法选择的下标值进行划分
    int partition2(int *arr, int l, int r){
    	int pid = getPivotId(arr, l, r);
    	swap(arr[l], arr[pid]);
    	int pivot = arr[l];
    	int i = l, j = r;
    	while(i < j){
    		for(; j > i; j--){
    			if(arr[j] < pivot){
    				arr[i++]= arr[j];
    				break;
    			}
    		}
    
    		for(; i < j; i++){
    			if(arr[i] > pivot){
    				arr[j--] = arr[i];
    				break;
    			}
    		}
    
    	}
    	arr[i] = pivot;
    	return i;
    }
    
    
    
    // 根据BFPRT算法求无序数组中第k小的数据
    
    int BFPRT(int *arr, int l, int r, int k){
    	int i = partition2(arr, l, r);
    	int p = i - l +1;
    	if(k == p) return arr[i];
    	else if(k < p) return BFPRT(arr, l, i-1, k);
    	else return BFPRT(arr, i+1, r, k-p);
    }
    
    
    // 用随机选择算法求取无序数组中最小的k个元素
    int BFPRT2(int *arr, int l, int r, int k, vector<int> &result){
    	int i = partition2(arr, l, r);
    	int p = i - l +1;
    	if(k == p){ 
    		for(int j = l; j <= i; j++)
    			result.push_back(arr[j]);
    		return arr[i];
    	}
    	else if(k < p){
    		return BFPRT2(arr, l, i-1, k, result);
    	}
    	else{
    		for(int j = l; j <= i; j++)
    			result.push_back(arr[j]);
    		return BFPRT2(arr, i+1, r, k-p, result);
    	}
    
    }

这里的时间复杂度为T(n) <= T(n/5)+T(7/10\*n)+O(n).分析如下：划分时以5个元素为一组取中位数，共得到n/5个中位数，再递归求取中位数，复杂度为T(n/5)。得到的中位数x作为主元进行划分，在n/5个中位数中，主元x大于其中1/2\*n/5=n/10的中位数，而每个中位数在其本来的5个数的小组中又大于等于其中的3个，所以主元x至少大于所有数中的n/10\*3=3/10\*n个。同理，主元x至少小于所有数中的3/10\*n个。划分后，任意一边的长度至少为3/10，在最坏情况下，每次选择都选到了7/10的那一部分，则递归复杂度为T(7/10\*n)。所以最终时间复杂度为上式。

参考：1：http://www.360doc.com/content/14/0905/10/11712807\_407176425.shtml

2：http://www.cricode.com/2001.html

[Center]: /images/20220806/bbb6b81f4e344f3ea1bbec85fb6e6a4c.png