算法导论 最坏情况为线性时间的选择算法 9.3-8 9.3-9

1.最坏情况为线性时间的选择算法

代码：

#include<iostream>
#include<stdlib.h>

using namespace std;

//1.把n个元素按每组k个元素划分为upfloor(n/k)组(k>3),最后一组元素个数可能小于k个
//2.利用插入排序InsertSort找到每组中的中位数
//3.递归调用Select从步骤2中找到的中位数组中找出其中位数

int Select(int * A, int p, int r, int t);

//插入排序，找到第t个顺序统计量
int InsertSort(int *A,int p,int r, int t)
{
	for(int i=p+1;i<=r;i++)
	{
		int key=A[i];
		int j=i-1;
		while(A[j]>key && j>=p)
		{
			A[j+1]=A[j];
			--j;
		}
		A[j+1]=key;
	}
	return A[p+t-1];
}

//找到中位数中的中位数
int Find(int *A,int p,int r,int k)
{
	int len=r-p+1;
	int *B=new int[len/k+1];//存储步骤2找到的中位数
	int j=0;
	int start=0, end=0;
	for(int i=0;i<len;i++)
	{	
		if (i%k==0)
			start=p+i;
		if(i%k==k-1 || i==len-1)
		{
			end=p+i;
			B[j]=InsertSort(A,start,end,(end-start)/2);
			++j;
		}
	}
	int mid=Select(B,0,j-1,j-1/2);
	delete []B;
	return mid;
}

//4.利用修改过的Partition版本，按中位数的中位数x对序列进行划分
//5.递归调用Select找到第t个顺序统计量

int Partition(int *A, int p, int r,int x)
{
	int k=0;
	for (int i=p;i<=r;i++)
	{
		if (A[i]==x)
			k=i;
	}
	int temp1=A[r];
	A[r]=A[k];
	A[k]=A[r];
	int l=p-1;
	for(int j=p;j<r;j++)
	{
		if(A[j]<A[r])
		{
			++l;
			int temp2=A[j];
			A[j]=A[l];
			A[l]=temp2;
		}
	}
	int temp3=A[r];
		A[r]=A[l+1];
		A[l+1]=temp3;
	return l+1;
}

int Select(int * A, int p, int r, int t)
{
	if (p==r)
		return A[p];
	int k=5;
	int x=Find(A,p,r,k);
	int q=Partition(A,p,r,x);
	int n=q-p+1;
	if (n==t)
		return A[q];
	else if (t<n)
		return Select(A,p,q-1,t);
	else
		return Select(A,q+1,r,t-n);
}

int main()
{
	int A[100]={0};
	for (int i=0;i<100;i++)
		A[i]=rand()%100;
	int res_i=Select( A, 0, 99, 50);
	cout<<res_i<<endl;
	return 0;
}

2.应用： 9.3-8

问题：两个包含n个有序元素的数组X,Y，设计一个O（lgn）时间的算法来找出数组X，Y中所有2n个元素的中位数。

思路：看到lgn，想到用分治法来做。分别调用Select找到X,Y的中位数midX,midY，若midX=midY，则中位数即为midX；若midX<midY,则对X的后半段和Y的前半段组成的两个数组递归找中位数；若midX>midY,则对X的前半段和Y的后半段组成的两个数组递归找中位数；直至，两个数组分别剩下两个元素，即总共有四个元素时，用插值法找到中位数。

代码：

int TwoVector(int *A,int p1,int r1,int *B,int p2,int r2,int n)
{
	if(r1==p1 && r2==p2)//基本情形我这里写了四种，感觉有点繁琐，不知道有没有更简便的方式
	{
		if (A[p1]<B[p2])
			return A[p1];
		else
			return B[p2];
	}
	if(r1==p1+1 && r2==p2)
	{
		int C[3]={0};
		C[0]=A[p1];C[1]=A[r1];
		C[2]=B[p2];
		int mid=InsertSort(C,0,2,2);
		return mid;
	}
	if(r1==p1 && r2==p2+1)
	{
		int C[3]={0};
		C[0]=A[p1];
		C[1]=B[p2];C[2]=A[r2];
		int mid=InsertSort(C,0,2,2);
		return mid;
	}
	if(r1==p1+1 && r2==p2+1)
	{
		int C[4]={0};
		C[0]=A[p1];C[1]=A[r1];
		C[2]=B[p2];C[3]=B[r2];
		int mid=InsertSort(C,0,3,2);
		return mid;
	}
	int midA=Select(A,p1,r1,n/2);
	int midB=Select(B,p2,r2,n/2);
	if(midA==midB)
		return midA;
	else if(midA<midB)
		return TwoVector(A,p1+n/2,r1,B,p2,p2+n/2-1,n/2);
	else
		return TwoVector(A,p1,p1+n/2-2,B,p2+n/2,r2,n/2);
}

int main()
{
	int A[50]={0},B[50]={0};
	for (int i=0;i<50;i++)
	{
		A[i]=rand()%100;
		B[i]=rand()%100;
	}
	InsertSort(A,0,49,1);
	InsertSort(B,0,49,1);
	int res=TwoVector(A,0,49,B,0,49,50);
	cout<<res<<endl;
	return 0;
}

3.应用：9.3-9

问题：见算法导论p125

思路：任意两点A,B连成的直线上，在两个点之间线段上任意取一点C，d（A,C）+d（B，C）最短且相等

             把所有油田看成在一条纵轴上，只要管道取为所有y的中位数即可得到最小总长度。若n为奇数，主管道位置唯一。若n为偶数，管道在n/2和n/2+1之间的位置（包括两个端点），总长度都最小。