一个C语言经典的分治问题
用分治方法,找出10个不同元素中第K个最小元素这是个数据放在一个数组啊a[10]里面,a[10]={3,6,5,56,48,1,34,78,99,0}求具体代码,运行成功...
用分治方法,找出10个不同元素中第K个最小元素
这是个数据放在一个数组啊a[10]里面,a[10]={3,6,5,56,48,1,34,78,99,0}
求具体代码,运行成功再追加分数!! 展开
这是个数据放在一个数组啊a[10]里面,a[10]={3,6,5,56,48,1,34,78,99,0}
求具体代码,运行成功再追加分数!! 展开
1个回答
展开全部
#include <stdio.h>
int partition(int a[],int low, int high)
{
int pivot = a[low];
int i=low;
int j=i+1;
for(;j<=high;++j)
{
if(a[j]<pivot)
{
++i;
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
int temp = a[i];
a[i]=pivot;
a[low]=temp;
return i;
}
int findKth(int a[],int low,int high, int k)
{
if(low==high)
return a[low];
int r = partition(a,low,high);
int i=r-low+1;
if(i==k)
return a[r];
else if(i<k)
findKth(a,r+1,high,k-i);
else
findKth(a,low,r-1,k);
}
int main()
{
int a[]={3,6,5,56,48,1,34,78,99,0};
for(int i=1;i<=10;++i)
{
int result = findKth(a,0,9,i);
printf("%dth->%d\n",i,result);
}
return 1;
}
《 算法导论》 中位数和顺序统计量 第二节有详细说明
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询