sel.cpp

通过精心挑选划分元素v

//////////////////////////////
//02级计科5班               // 
//学号：200231500170        //
//姓名：李娜                //  
//////////////////////////////

///////////////////////////////////////////////////////////////
//程序功能描述：                                             //
//输入一组数，返回A[i],使其为A(m:p)中第k小的元素，k是一个全局//
//变量，取大于1的整数                                        //     
///////////////////////////////////////////////////////////////
#include<stdio.h>

//插入排序，将B(e:f)中的元素按非降次序排列
void INSERTIONSORT(int B[],int e,int f)
{
	int item,i,j;
	for(j=e+1;j<=f;j++)
	{ 
		item=B[j];
		i=j-1;                          //要开始比较B[j]和B[j-1]
		while(item<B[i]&&i>=e) 
		{
			B[i+1]=B[i];
			i--;                       //如果item小则将大的往后移，直到找到item的合适位置
		}
		B[i+1]=item;                   //否则直接保持B[j]的位置不变
	}

}

//交换两个元素的位置
void INTERCHANGE(int &c,int &d)
{
	int k;
    k=c;
	c=d;
	d=k;
}


////////////////////////////////////////////////////////////////
//划分算法,将B[e],B[e+1],...B[f]中的元素按如下方式重新排列    //
//如果最初划分元素为v=B[e],则在重排后对于e和f之间的某个q,     //
//有B[q]=t，并使得对于e<=k<q,有B[k]<=t，而对于q<k<=f,有B[k]>=t//
//退出过程时，f带着划分元素所在的下标，即q的值返回            //
////////////////////////////////////////////////////////////////
int PARTITION(int B[],int e,int f)
{
	int v,i;
	v=B[e];i=e;                       //B[e]是划分元素
	f++;
	while(1)
	{
		while(B[++i]<v);             //i由左向右移
		while(B[--f]>v);             //p由右向左移　
		if(i<f) INTERCHANGE(B[i],B[f]);//B[i]和B[f]换位
		else break;
	}
	B[e]=B[f];
	B[f]=v;
	return(f);
}

//////////////////////////////////////////////////////
//返回一个j, 使得m<=j<=p,且A[j]是A(m:p)中第k小的元素//
//////////////////////////////////////////////////////
int SEL2(int A[],int m,int p,int k)
{
  int n,i,j;
  int r=5;
  int e;
  int w;
  while(1)
  {
	  if(p-m+1<=r) 
	  {
		  INSERTIONSORT(A,m,p);
		  return(m+k-1);
	  }
	  n=p-m+1;
	  for(i=1;i<=(n/r);i++)
	  {
		  INSERTIONSORT(A,m+(i-1)*r,m+i*r-1);    //将中间值收集到A(m:p)的前部//
		  INTERCHANGE(A[m+i-1],A[m+(i-1)*r+r/2]);
	  }
	  if ((n/r/2.0)!=(n/r/2))
		  w=n/r/2+1;
	  else
		  w=n/r/2;                              //取上整
	  j=SEL2(A,m,m+n/r-1,w);                    //mm//
	  if(m!=j) INTERCHANGE(A[m],A[j]);          //产生划分元素
	  j=PARTITION(A,m,p);
	  e=j-m+1;
	  if(e==k) 
		  return(j);
	  else 
	  {
		  if(e>k) p=j-1;
		  else 
		  {
			  k=k-e;m=j+1;
		  }
	  }
  }
}
 
//主函数 
void main()
{
	int A[128];
	int k,x,a=0;
	int t=0,j;
	printf("************最坏情况是o(n)的选择算法(select2的实现)*********\n");
	printf("请输入这组数的个数(<=128):");
	scanf("%d",&x);
	while(x<=0||x>=128)
	{
		printf("请输入一个<=128的正整数：");
		scanf("%d",&x);
	}
	for(;t<x;t++)
	{
		printf("请输入这组数:");
		scanf("%d",&A[t]);
	}
	printf("请输入选择第几小的元素:");
	scanf("%d",&k);
	printf("\n");
	while(k>x||k<=0)
	{
		printf("输入有误,请重新输入:");
		scanf("%d",&k);
	}
	t--;
	j=SEL2(A,a,t,k);
	printf("第%d小的元素为:%d\n",k,A[j]);
}