sy4.cpp

分治法寻找第K小元素

#include <iostream>
using namespace std;
void Merge(int r1[],int r[],int s,int m,int t);

void MergeSort(int r[],int r1[],int s,int t)
{
	int m=(s+t)/2;
	if(s==t) r1[s]=r[s];
	else
	{	
	    MergeSort(r,r1,s,m);
		MergeSort(r,r1,m+1,t);
		Merge(r1,r,s,m,t);
       	
	}
	for(int n=s;n<=t;n++)
	{
	  r[n]=r1[n];
	}
}
void Merge(int r1[],int r[],int s,int m,int t)
{
	int i=s;
	int j=m+1;
	int k=s;
	while(i<=m&&j<=t)
	{
		if(r[i]<r[j])
		{
			r1[k++]=r[i++];
		}
		else
		{
			r1[k++]=r[j++];
		}
	}
	while(i<=m)
	{
		r1[k++]=r[i++];
	}
	while (j<=t)
	{
		r1[k++]=r[j++];
	}

}
//寻找第K小元素，可以先将要找的元素进行排序，再返回排序后数组中的第K个元素就是第K小元素，（这里相同元素按排序先后分成不同大小）
int searchK(int r[],int n,int k)
{
    int *a=new int[n];
    int r1[100];
	MergeSort(r,r1,0,n-1);
    return (k-1);
}
void main()
{
	int k;
	int r[10]={3,12,36,35,67,43,35,78,90,203,};
	cout<<"请输入K的值：";
	cin>>k;
    int i=searchK(r,10,k);
    cout<<"第K小元素为："<<r[i]<<endl;
}