线性时间求第k小（分治思想）

旧城等待， 2024-02-18 16:17 15阅读 0赞

方法：将序列5个一组进行分组，找出每组得中位数，在从这些中位数中找出中位数（递归找出，当元素个数小于75时，则采用简单排序进行排序，将第k小值返回），作为划分元素（快排划分思想）。O(n)的由来：只要能保证两边划分的元素比大于1/10，试验得出的结论是可以看作O(n)的(在数据量很大的情况下)。

产生20000个随机数，任意输入k的值，输出结果。另输出前200小的数做验证：

#include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    const int maxn=20000+10;
    int a[maxn];
    
    int Partition(int p,int r,int X){  //划分 
        int i = p;
    	int j = r,x = X;
    	while(i<j){
    	  while(j>=p && a[j]>x)j--;
    	  if(i < j){
    	  	a[i++] = a[j];
    	  }
    	  while(i<=r && a[i]<x)i++;
    	  if(i < j){
    	  	a[j--] = a[i];
    	  }
    	}
          a[j] = x;
    	return j;
    }
    
    
    int Select(int p,int r,int k){
    	if(r - p < 75){
    		sort(a+p,a+r);
    		return a[p+k-1];
    	}
    	
    	for(int i = 0; i <= (r-p-4)/5; i++){
    		sort(a+i*5,a+i*5+5);
    	}
    	
    	for(int i = 0; i <= (r-p-4)/5; i++){  //每一组的第三小与a[i+p]交换 
    		int temp = a[i+p]; a[i+p] = a[i*5+2+p]; a[i*5+2+p] = temp;
    	}
    	
    	int x = Select(p,p+(r-p-4)/5,(r-p-4)/10);
    	int i = Partition(p,r,x) , j = i - p + 1;
    	if(k <= j) return Select(p,i,k);
    	else return Select(i+1,r,k - j);
    }
    
    int main(){
    	int k ;
    	printf("请输入第k小:");
    	scanf("%d",&k);
    	printf("\n");
    	//产生20000个随机数 
    	for(int i = 0; i < 20000; i++){
    		a[i] = rand();
    	}
    	
    	printf("第k小的数：%d\n\n",Select(0,20000,k));
    	
    	printf("输出前200小的数：\n");  //作为验算正确性 
    	sort(a,a+20000);
    	for(int i = 0; i < 200; i++)
    	{
    		if(i%10 == 0)printf("\n");
    		printf("%6d",a[i]);
    	}
    	printf("\n");
    	return 0;
    }

![Center][]

[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a46e715c137d427f81a405f5aee26445.png