算法导论第九章习题9.3-7

在O(n)时间范围内找出数组a[n]中位数相邻的k个数字

思路：简单的思路是先找出中位数（n+1）/2然后依次找第（n+1）/2-1小数字、（n+1）/2-2小数字、（n+1）/2-3.小数字。。。。（n+1）/2-k/2小数字，再找第（n+1）/2+1小数字、（n+1）/2+2小数字、（n+1）/2+3.小数字。。。。（n+1）/2+（k+1）/2小数字。但是该算法时间复杂度为O(kn)。

改进思路为：先找中位数，将数组按照中位数进行分割，数组的前半部分找第（n-1）/2-k/2小的数字，按照该数字对前半部分进行分割，则该数字到中位数之前的数字有k/2个数字，这些数字为与中位数相邻且小于中位数的前k/2个数字。数组的后半部分找出第（k+1）/2小的数字，然后按照该元素对后半部分进行分割，则中位数后一元素到该元素的（k+1）/2个元素为与中位数相邻且大于中位数的数字。该算法共调用三次分割选择函数Select，而该函数的时间复杂度为O(n)，所以时间复杂度为O(n)。其具体代码如下：

//例题9.2中的算法的期望时间复杂度为O(n)，而在9.3的例题中的最坏运行时间复杂度为O(n)。
//该算法实现思路是将数组每五个元素分为一组，最后一组可能不足五个。
//选出每一组中的中位数，然后选出这些中位数的中位数。根据这个中位数对数组进行划分为两组。
//然后再按照9.。2中的方法递归调用划分寻找第i小的数。
//该算法的对比于9.2的改进之处在于对partition方法进行了优化，而不是随进选择数组进行划分。
#include<iostream>
using namespace std;
//插入排序不解释
void Insert_sort(int a[],int p,int r)  
{  
    int i,j,key,length;
	length=r-p+1;
    for(i=p+1;i<=r;i++)  
    {  
        key=a[i];  
        j=i-1;  
        while(key<a[j])  
        {  
            int temp;  
            temp=a[j+1];  
            a[j+1]=a[j];  
            a[j]=temp;  
            j=j-1;  
            if(j<p)  
            {  
                break;  
            }  
        }  
    }  
}  
//按照中位数的中位数进行分割
int Partition(int a[] ,int p,int r)
{
	int i=p,j=0,temp,num,b[100];
	//将a中每五个元素进行插入排序，并找出五个元素中的中位数放到b中
	while(1)
	{
		if(i>r)
		{
			break;
		}
		if((i+4)<=r)
		{
			Insert_sort(a,i,i+4);
			b[j++]=a[i+2];
		}
		else
		{
			Insert_sort(a,i,r);
			b[j++]=a[(r+i)/2];
		}
		i+=5;
	}
	j=j-1;
	//对b中的元素进行排序
	Insert_sort(b,0,j);
	//找到b中的中位数
	num=b[j/2];
	//将a中的num与a[r]替换
	for(i=0;i<=r;i++)
	{
		if(num==a[i])
			break;
	}
	temp=a[i];
	a[i]=a[r];
	a[r]=temp;
	//根据找到的num对数组进行划分
	j=p-1;
	for(i=p;i<r;i++)
	{
		if(a[i]<num)
		{
			j++;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	temp=a[r];
	a[r]=a[j+1];
	a[j+1]=temp;
	return j+1;
}
//按照特定的数字num进行分割
int Partition1(int a[] ,int p,int r,int num)
{
	int i,j=0,temp;
	//将a中每五个元素进行插入排序，并找出五个元素中的中位数放到b中
	
	//将a中的num与a[r]替换
	for(i=0;i<=r;i++)
	{
		if(num==a[i])
			break;
	}
	temp=a[i];
	a[i]=a[r];
	a[r]=temp;
	//根据找到的num对数组进行划分
	j=p-1;
	for(i=p;i<r;i++)
	{
		if(a[i]<num)
		{
			j++;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	temp=a[r];
	a[r]=a[j+1];
	a[j+1]=temp;
	return j+1;
}
//选择第num小的数字
int Select(int a[],int p,int r,int num)
{
	if(p==r)
	{
		return a[p];
	}
	int q=Partition(a,p,r);
	int k=q-p+1;
	if(k==num)
	{
		return a[q];
	}
	else if(num<k)
	{
		return Select(a,p,q-1,num);
	}
	else
	{
		return Select(a,q+1,r,num-k);
	}
}
void SelectKthNearTheMiddle(int a[],int b[],int p,int r,int k)
{
	int i,j;
	if(k<=0)
	{
		cout<<"wrong number!"<<endl;
		return ;
	}
	int length,t,s,q;
	length=r-p+1;
	//找出中位数为第(length+1)/2小的数字
	s=Select(a,p,r,(length+1)/2);
	//本来打算调用Partition1将数组从s值处分割为两部分
	//调试时发现该步骤 是多余的，因为在Select(a,p,r,(length+1)/2)中已经
	//把数组按照s分割为两部分了，下面调用的两Select跟此处的一样，不用再调用Partition1
	//Partition1(a,p,r,s);

	//在中位数之前的数组中找出第(length-1)/2-(k)/2+1的元素
	//该元素到中位数之前的数字为接近中位数的k/2个数字
	t=Select(a,p,p+(length-1)/2-1,(length-1)/2-(k)/2+1);
	//找出中位数之后数组中第（k+1）/2小的元素，中位数之后起的第一个数字到该元素为
	//接近中位数的（k+1）/2个数字
	q=Select(a,p+(length-1)/2+1,r,(k+1)/2);
	//将中位数元素前一个元素到t赋给数组b的前半部分，此复制为倒序，所以j是从(k)/2-1开始到0的
	j=(k)/2-1;
	for(i=p+(length-1)/2-1;i>=p+(length-1)/2-(k)/2;i--)
	{
		b[j--]=a[i];
	}
	//将中位数元素后一个元素到q赋给b的后半部分
	j=(k)/2;
	for(i=p+(length-1)/2+1;i<=p+(length-1)/2+(k+1)/2;i++)
	{
		b[j++]=a[i];
	}
}

int main()
{
	int a[15]={16,48,748,742,1635,2,56,48,685,4596,3,4,1,6,5};
	int b[100];
	SelectKthNearTheMiddle(a,b,0,14,5);
	for(int i=0;i<5;i++)
	{
		cout<<b[i]<<" ";
	}
	cout<<endl;
	return 0;
}