2615: 分治策略-改进的线性时间选择（每5个一组）

#include <stdio.h>

int partition(int a[], int low, int high, int x) {
	int i = low;
	int j = high;
    for(int k=low; k<=high; k++){ 
    // 查找x并与a[low]进行交换 
    	if(a[k]==x){
    		int t=a[k];
			a[k]=a[low];
			a[low]=t; 
			break;
		}
	}
	while (i<=j) {
		while(i<=j && a[i]<=x) i++;
		while(i<=j && a[j]>x) j--;
		if(i<j) {
			int temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	a[low]=a[j];
	a[j]=x;
	return j;
}

void bubble(int a[],int low,int high) { 
    // 对low到high之间的元素进行简单选择排序 
	int i,j;
	for(i=low; i<=high-1; i++) {
		int index=i;
		for(j=i+1; j<=high; j++)
			if(a[j]<a[index]) index=j;
		int t=a[i];
		a[i]=a[index];
		a[index]=t;
	}
}

int select(int a[],int low,int high,int k) {
	if(high-low+1<10) { 
        // 递归出口，如果不足10个元素则直接排序之后得到结果 
		bubble(a,low,high);
		return a[low+k-1];
	}

    //每组5个元素，不足5个元素的最后一组暂时不考虑
	for(int i=0; i<=(high-low-4)/5; i++) {
		
	}

	//寻找中位数的中位数
	int x=select(a,low,low+(high-low-4)/5,(high-low+1)/10); 
	int i=partition(a,low,high,x);
	int length=i-low+1;

	if(k<=length)
	{
		return select(a,low,i,k);
	} 
	else
	{
		return select(a,i+1,high,k-length);
	}
	
}

int main(void) {
	int a[100],i,n,k;
	scanf("%d",&n);
	for(i=0; i<=n-1; i++) scanf("%d",&a[i]);
	scanf("%d",&k);
	int result=select(a,0,n-1,k);
	printf("%d\n",result);
	return 0;
}

22
11 13 12 14 15 16 17 19 18 20 21 1 2 3 4 5 6 7 8 9 10 -1
12

11